소수 구하기 (에라토스테네스의 체)

 

1929번: 소수 구하기

🤔생각해보기

문제는 간단하다. 에라토스테네스의 체를 사용해서 풀면 된다.

개인적으로 소수 구하는 문제에서 자주 쓰는 방법은 제곱근까지만 약수의 여부를 검증해서 O(logN)의 시간 복잡도로 구하는 것이다.

에라토스테네스의 체는 다량의 소수를 한 번에 판별할 때 쓰면 좋은 방식으로 자세한 내용은 다음을 참고하자.

위키독스

 

m, n = map(int, input().split())
a = [False, False] + [True] * (n - 1)
prime = []

for i in range(2, n + 1):
    if a[i]:
        prime.append(i)
        # range의 3번째 인자 i는 i만큼 건너뛰면서 루프를 진행하게 한다.
        for j in range(2 * i, n + 1, i):  
            a[j] = False

for num in prime:
    if num >= m:
        print(num)