[백준/파이썬] 1929번 - 소수 구하기

문제 설명

풀이 전략

N,M이 최대 1,000,000이므로 O(NlogN)이하의 알고리즘을 사용하여야 시간 초과가 생기지 않을 수 있다. 소수를 구하는 문제에서 사용할 수 있는 전략은 1. 수의 제곱근까지 검사하는 방법 2. 에라토스테네스의 체를 이용하는 방법이 있다. 이 중 에라토스테네스의 체를 이용하는 것이 더 효율적이다.

코드

1. 제곱근까지 체크

m,n=map(int,input().split())

for i in range(m,n+1):
    if i > 1:
        flag = 0
        for j in range(2,int(i**0.5)+1):
            if i % j == 0:
                flag = 1
                break
        if flag == 0:
            print(i)

2. 에라토스테네스의 체

m,n = map(int,input().split())

sieve = [False, False] + [True] * (n-1)
arr=[]
for i in range(2,n+1):
    if sieve[i]:
        for j in range(2*i,n+1,i):
            sieve[j] = False
        if i >= m:
            arr.append(i)
for i in arr:
    print(i)

결과를 비교해 보면 에라토스테네스의 체를 이용한 방식이 실행 시간이 훨씬 짧은 것을 볼 수 있다.