baekjoon 1929: 소수 구하기

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

1929번: 소수 구하기

---

위 문제는 소수를 구하는 문제인데, 입력값이 1,000,000까지 존재하고, 제한시간이 2초 이므로, 시간적인 여유가 많이 없으므로 단순구현이 아닌 알고리즘이 필요하다. 

 

이에 내가 선택한 알고리즘은 에라토스테네스의 체 라는 알고리즘인데

 

해당 수까지 전체 for문을 돌며 소수임을 확인하는 것이 아닌, 작은수부터 for문을 돌려 소수를 찾고, 찾은 소수를 배수시키며 check해준다.

 

check된 수는 소수가 아니므로 for문을 돌 지 않아도 됨

 

따라서 시간적인 여유가 생김!

m,n = list(map(int,input().split()))
prime = []
check = [0]*(n+1)
for i in range(2,n+1):
    if not check[i]:
        prime.append(i)
    for j in range(i+i,n+1,i):
        check[j] = 1
for i in range(len(prime)):
    if m<=prime[i]<=n:
        print(prime[i])