[Python] 백준 #1929 소수 구하기

www.acmicpc.net/problem/1929

1929번: 소수 구하기

정답률이 적은 문제는 그 이유가 있는법..

시간초과 자슥 ㅠㅠㅠㅠㅠ

시간복잡도에 대해 더 깊게 공부해야겠다

 

이건 쉽게 생각할 수 있는 코드로 짰더니 시간 초과가 발생했다

#시간초과!!!!
n,m=map(int,input().split())

for i in range(n,m+1):
    if i==1:
        continue
        
    k=0
    for j in range(2,i):
        if i%j==0:
            k+=1
    if k==0:
        print(i)

에라토스테네스의 체 알고리즘으로 구해봤다 nlognlogn

wikidocs.net/21638

 

1. 1은 제거

2. 지워지지 않은 수 중 제일 작은 2를 소수로 채택하고, 나머지 2의 배수를 모두 지운다.

3. 지워지지 않은 수 중 제일 작은 3을 소수로 채택하고, 나머지 3의 배수를 모두 지운다.

4. 지워지지 않은 수 중 제일 작은 5를 소수로 채택하고, 나머지 5의 배수를 모두 지운다.

5. (반복)

위키독스

#에라토스테네스의 체 알고리즘 : 시간 복잡도 = O(Nlog(logN))
#위의 방법은 범위 안에서의 소수를 구할때는 효율적인 방법이아님. 에라토스로 구해보자
import sys

n,m=map(int,sys.stdin.readline().split())
List=[1]*(m+1)
List[0]=0
List[1]=0


for k in range(2,m+1):
    if List[k]==1: #지워지지않음
        for i in range(k*2,m+1,k):
            List[i]=0

for i in range(m+1):
    if i>=n and i<=m and List[i]==1:
        print(i)