[파이썬] 백준 - 15단계 약수,배수와 소수2

[파이썬] 백준 - 15단계 약수,배수와 소수2

 

유클리드 호제법 / 에라스토테네스의 체 / 소수는 제곱근 까지 탐색

---

 

최소공배수 (1934)

T = int(input())
for i in range(T):
    A,B = map(int,input().split())
    if min(A,B)==1 :
        print(max(A,B))
        continue
    else :
        for j in range(min(A,B),0,-1):
            if A%j == 0 and B%j == 0:
                print(int(A*B/j))
                break

1초 정도면 그냥 넘어갈줄 알고 최소공배수 구했는데 시간초과

두 수의 곱이 최대공약수로 나누어 떨어지면 출력

---

최소공배수 (13241)

A,B = map(int,input().split())
if min(A,B)==1 :
    print(max(A,B))
else :
    for j in range(min(A,B),0,-1):
        if A%j == 0 and B%j == 0:
            print(int(A*B/j))
            break

---

분수 합 (17350)

x1,x2 = map(int,input().split())
y1,y2 = map(int,input().split())    
up = x1*y2 + x2*y1
down = x2*y2

def gcd(a, b):
    while b>0 :
        a,b = b,a%b
    return a
d = gcd(up,down) 
print(int(up/d),int(down/d))

유클리드 호제법으로 최대공약수 구하고 분자 분모 나눴습니다

 

---

가로수 (2485)

import sys
import math
N = int(sys.stdin.readline())

temp,tree = [],[]
for i in range(N):
    if i==0:
        a = int(sys.stdin.readline())
        tree.append(a)
    else :
        b = int(sys.stdin.readline())
        tree.append(b)
        temp.append(b-a)
        a = b
temp = sorted(list(set(temp)))

d = math.gcd(*temp)
answer = int((tree[-1]-tree[0])/d)-len(tree)+1
print(answer)

gcd에 int 말고 list넣고 * 써주면 리스트 언패킹돼서 한 번에 진행 가능.

---

다음 소수 (4134)

def is_prime(x):
    if x<2 :
        return False
    for i in range(2,int(x**(1/2))+1):
        if x%i == 0:
            return False
    return True

test = int(input())
for i in range(test):
    n = int(input())
    while True :
        if is_prime(n) == True :
            break
        else : 
            n += 1
    print(n)

---

소수구하기 (1929)

def prime_list(n):
    num = [True]*n
    for i in range(2,int(n**(1/2))+1) :
        if num[i] == True : 
            for j in range(i+i,n,i) :
                num[j] = False
    return [i for i in range(2,n) if num[i] == True]

m,n = map(int,input().split())
for i in prime_list(n+1) :
    if i >= m :
        print(i)

---

베르트랑 공준 (4948)

def prime_list(n):
    num = [True]*n
    for i in range(2,int(n**(1/2))+1) :
        if num[i] == True :
            for j in range(i+i,n,i) :
                num[j] = False
    return [i for i in range(2,n) if num[i]==True]

while True :
    n = int(input())
    if n==0 :
        break
    else :
        answer = list(filter(lambda x: x>n,prime_list(2*n+1)))
        print(len(answer))

 

---

골드바흐 파티션 (17103) :

N = int(input())

def prime_list(n):
    temp = [True]*n
    for i in range(2,int(n**(1/2))+1):
        if temp[i] == True :
            for j in range(i+i,n,i):
                temp[j] = False
    return [i for i in range(2,n) if temp[i]==True]

temp = []
for i in range(N):
    a = int(input())
    temp.append(a)
prime = prime_list(max(temp))

for i in temp :
    count = 0
    for j in [num for num in prime if num <= i/2] :
        if i-j in prime :
            count += 1
        if j >= (i/2) :
            break
    print(count)

에라스토테네스 시간복잡도가 낮아서 반복문 안에서 그냥 돌렸는데 다른 문제보다 시간제한이 빡세서 시간초과.

input 값에서 가장 큰 값으로 소수 리스트를 만들어두고 쓰기 / 소수 매칭 시 쌍으로 세기 때문에 절반만 탐색하기

했는데 안돼서 나중에 풀기

---

창문 닫기 (13909)

n = int(input())
answer = [i for i in range(1,int(n**(1/2)+1))]
print(len(answer))