#1929 소수 구하기

#1929 소수구하기 문제 보러가기

리스트의 인덱스로 수를 표현하는 방법과 이중 for문을 사용해서 문제를 해결하고 싶었으나, 예상한 대로 시간초과가 발생했다.

import sys

M,N=map(int,sys.stdin.readline().split())
num_list=[0]*(N-M+1)
for i in range(M,N):
    for j in range(2,i):
        if i%j==0:
            num_list[i-M]+=1

for i in range(M,N):
    if num_list[i-M]==0:
        print(i)

• 해당 수보다 작은 모든 수로 나누어 보아서 소수인지를 판단하는 방법은 시간초과가 발생한다. 따라서 효율적으로 소수를 구하기 위해 '에라토스테네스의 체'라는 방법을 사용한다.

에라토스테네스의 체

• 범위에서 합성수를 지우는 방식으로 소수를 찾는 방법.

1. 1은 제거
2. 지워지지 않은 수 중 제일 작은 2를 소수로 채택하고, 나머지 2의 배수를 모두 지운다.
3. 지워지지 않은 수 중 제일 작은 3을 소수로 채택하고, 나머지 3의 배수를 모두 지운다.
4. 지워지지 않은 수 중 제일 작은 5를 소수로 채택하고, 나머지 5의 배수를 모두 지운다.
5. (반복)
   

n=1000
a = [False,False] + [True]*(n-1)
primes=[]
n+1
for i in range(2,n+1):
  if a[i]:
    primes.append(i)
    for j in range(2*i, n+1, i):
        a[j] = False
print(primes)

위 방법으로 백준 #1929 소수 구하기를 해결할 수 있다. 파이썬 코드는 다음과 같다.

import sys, math

M,N=map(int,sys.stdin.readline().split())
num_list=[False,False]+[True]*(N-1)
primes=[]

for i in range(2,N+1):
    if num_list[i]:
        primes.append(i)
        for j in range(2*i,N+1,i):
            num_list[j]=False

for i in primes:
    if i>=M:
        print(i)

참고문헌
https://wikidocs.net/21638