1929번 소수 구하기

소수 구하기

풀이

에라토스테네스의 체를 이용해서 이하의 모든 정수에 대해 소수인지 체크한 다음 이상 이하의 정수 중 소수인 것을 모두 출력하면 됩니다.

시간 복잡도는 입니다.

코드

def main():
    M, N = map(int, input().split())
 
    is_prime = [True] * (N + 1)
 
    is_prime[1] = False
    for i in range(2, N + 1):
        if not is_prime[i]:
            continue
 
        for j in range(i + i, N + 1, i):
            is_prime[j] = False
 
    for i in range(M, N + 1):
        if is_prime[i]:
            print(i)
 
 
main()