[백준] 1929번 (python 파이썬) 소수구하기

시간초과를 조심해야하는 문제이다.

어떤 수를 배수로 가지는 수는 소수가 아님을 이용하면 되는데

그 점을 이용하면 확인하려는 수의 제곱근까지만 확인하면 된다.

def is_prime(n):
    if n < 2: # 1은 소수가 아님
        return False
    for i in range(2, int(n**0.5) + 1): # 제곱근까지만 확인
        if n % i == 0:
            return False
    return True # 나누어 떨어지는 수가 없었다면 소수
M, N = map(int, input().split())

result = []
for n in range(M, N + 1):
    if is_prime(n):
        result.append(n)
        
print('\n'.join(map(str, result))) #시간 단축

이렇게 푼다면 통과는 되지만 시간이 오래걸리는 것을 알 수 있다.

 

더 시간을 단축하기 위해서는 에라토스테네스의 체 라는 것을 이용하면 된다.

간단하게 설명하자면 "어떠한 수를 갖는 배수를 지워나가면 소수만 남는다" 라는 것이다.

728x90

1부터 40까지 그림으로 대충 보여주자면 이렇게 어떠한 수를 배수로 갖는 수를 지워주면 소수만 남는 것을 확인 할  수 있다.

MAX = 1000000
check = [0] * (MAX + 1) # 소수인지 아닌지 확인
check[0] = check[1] = True # 소수가 아니므로 미리 True로 만들어줌

for i in range(2, MAX + 1):
    if not check[i]: False라면
        j = i + i # 배수에 접근하기 위해서
        while j <= MAX:
            check[j] = True #소수가 아닌것
            j += i # 배수를 늘려줌
            
m, n = map(int, input().split())
for i in range(m, n + 1):
    if check[i] == False: #소수일때만
        print(i)

입력에 주어진 범위까지 미리 에라토스테네스의 체를 활용하여 소수인지 아닌지 표시하고 소수일때만 출력하도록 해주면 월등히 속도가 빠른 것을 확인할 수 있다.