백준 알고리즘 1929 소수 구하기

문제

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

입력

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

출력

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

예제 입력 

3 16

예제 출력 

3
5
7
11
13

  그냥 풀면 시간초과가 난다. 그냥 파이썬으로 소수를 구하려면 시간이 오래 걸리나보다.

에라토스테네스의 체를 사용하면 보다 빠르게 소수를 구할 수 있다.

소수는 1과 자기 자신으로만 나눠질 수 있는 수이다. 거꾸로 생각하면 어떤 수의 배수는 소수가 될 수 없다는 것이다.

그렇다면 어떤 수의 배수를 다 지워나가면 결국 남는 건 소수가 될 것이다.

M,N = map(int,input().split())
num = [x for x in range(1, N+1)] #1~N까지 리스트, 2를 제외한 2의 배수 삭제, 3을 제외한 3의 배수 삭제...
num.insert(0,1)#0번째에 1넣어서 숫자와 인덱스를 맞춤
for i in range(2,N+1): #인덱스 2부터 시작, 인덱스 2의 값은 2임. 1부터 시작이라면 모든 수가 1이 됨.
    j = 2 #자기 자신보다 큰 배수이므로 2배부터 시작
    while N>=i*j: #i의 배수가 N보다 작거나 같을 때
        num[i*j] = 1 #i보다 큰 i의 배수를 1로 만듦
        j+=1 #다음 배수로 이동
for l in num: #1과 소수가 섞인 리스트
    if l!=1 and M<=l and l<=N: #1이 아닌 M이상 N이하의 수
        print(l,end=',')