[python][BOJ1929] 소수 구하기

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

1929번: 소수 구하기

 

 

for문을 돌려가며 각 수를 소수인지 아닌지 판별하는 방법은 시간복잡도가 O( (N-M)² ) 이므로 M=1, N=1,000,000인

경우에는 시간초과가 난다. 그러므로 '에라토스테네스의 체'를 변형해서 2 ≤ i ≤ N+1, 2 ≤ j ≤ N+1(i*j ≤ N) 의 범위에서

bool리스트[i*j]=False로 지정해주면 된다.

 

에라토스테네스의 체에 관한 내용은 아래 링크에 있다.

https://ujoon.tistory.com/7

[이론] 에라토스테네스의 체

 

코드는 아래에 있다.

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

isPrime=[True]*(N+1)
isPrime[1]=False

for i in range(2,N+1):
    for j in range(2,N+1):
        if i*j>N:
            break
        isPrime[i*j]=False

for i in range(M,N+1):
    if isPrime[i]:
        print(i)