백준 알고리즘 1929 (소수 구하기) - python

[문제] 백준 알고리즘 1929 (소수 구하기)

> https://www.acmicpc.net/problem/1929

1929번: 소수 구하기

 

에라토스테네스의 체를 이용하라는 문제이다.

 

소수를 구하기 위해 합성수를 제거하는 방식으로, 2부터 N까지 배수를 제거한다.

2부터 N까지의 소수를 구하기 위해선, N의 제곱근까지만 검사하면 된다.

range(N)이 N-1까지이고, 배열이 0부터 시작하는 특성상, 받아온 N을 +1 해주는 트릭을 썼다.

 

[Code]

M, N = map(int, input().split())

def prime_sieve(M, N):
    N += 1
    sieve = [True] * N
    for i in range(2, int(N**0.5)+1):
        if sieve[i]:
            for j in range(2*i, N, i):
                sieve[j] = False
    for i in range(M, N):
        if i > 1:
            if sieve[i]:
                print(i)

prime_sieve(M, N)