[BOJ]1929. 소수 구하기

문제:

M이상 N이하의 소수를 모두 출력하는 프로그램을 작성하시오.

입력:

첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1<=M,N<=1,000,000)

출력:

한 줄에 하나씩, 증가하는 순서대로 소수를 출력한다.

풀이 방법:

임의의 수 n이 소수인지 판별하기 위해서 n-1까지 다 나눠보는 것이 아니라 sqrt(n) 값까지 나눠서 나누어지지 않는다면 소수임을 알 수 있다는 것은 대부분 알고 있다. 하지만 1,000,000개의 수에 대해서 다 해보는 것은 아무리 sqrt(n) 값까지 나눠본다고 해도 많은 시간이 소요된다. 따라서 이렇게 큰 수가 소수인지 판별하기 위해서 사용되는 것이 에라토스테네스의 체이다.

 이 방법은 예를 들어 120이하의 소수들을 파악하기 위해서 120까지의 배열을 생성한 뒤에 우선 2가 소수인지 판별을 한다. 2는 소수인것이 자명하므로 2의 배수의 값을 0으로 바꾼다.(4,6,8,10,12,14,......) 다 바꾸고 난 뒤에 3도 소수이므로(쉽게 판별할 수 있다.) 3의 배수의 값들을 0으로 바꾼다.(6,9,12,15,.....)이후 원래 4의 값으로 이동을 했지만 이미 2의 배수의 경우일 때 0으로 바뀌어 있다. 0이면 어떤 소수의 배수임을 의미하므로 그냥 지나가게 설정을 한다. 이렇게 계속 0이 아닌 수를 만나면 소수인지 판별을 하고 0을 만나면 그냥 지나가도록 한다. 그러면 최종적으론 이 배열엔 소수와 0만 남아있는 배열이 된다.

그러면 set을 통해서 중복된 0의 값들을 다 제거하고 재정렬한뒤 0의 값을 빼준다면 소수만 남아있는 리스트가 된다. 따라서 이 문제도 에라토스테네스의 체 방법을 이용해서 풀면 시간초과가 발생하지 않고 풀 수 있다.

import math
def prime(n):
    is_prime=True
    if n==1:
        is_prime=False
    for i in range(2,int(math.sqrt(n))+1):
        if n%i==0:
            is_prime=False
    return is_prime
a,b=input().split()
a=int(a)
b=int(b)
h=list(range(1,b+1))
h[0]=0
for i in range(len(h)):
    if h[i]==0:
        pass
    elif prime(h[i]):
        for j in range(i+h[i],len(h),h[i]):
            h[j]=0
h=sorted(list(set(h[a-1:])))
h.remove(0)
for i in h:
    print(i)