[Python] 1929 소수구하기

문제보기

문제코드

M, N = map(int,input().split())

sosu = []

for i in range(M,N+1):
    if i > 1:
        for j in range(2,i):
            if i%j==0 :
                break
        else :
            sosu.append(i)
if len(sosu) ==0:
    print("-1")
else:
    for i in range(len(sosu)):
            print(sosu[i])

검사하여 리스트에 추가하고 리스트를 출력하니 시간초과가 떴다.

이는 반복문을 통해 소수를 출력하는 것이 아닌

해결코드

M, N = map(int,input().split())

for i in range(M,N+1):
    if i > 1:
        for j in range(2, int(i ** 0.5) + 1):
            if i%j==0:
                break
        else :
            print(i)

과 같이 제곱근 까지만 반복하여 소수를 판별하는 에라토스테네스의 체 를 이용하여 소수를 판별해야했다.

에라토스테네스의 체란?

출처 : [백준] 1929번 : 소수 구하기 (파이썬)

소수를 판별해주는 알고리즘

1. 1부터 12 사이의 소수를 판별해본다.
2. 1은 소수가 아니므로 2부터 시작한다.
3. $12<4^2$이므로 4 (int(sqrt(12))=3) 보다 작은 수의 배수만 제거하면 된다. (즉, 3까지만 계산)

예시

자기자신을 제외한 2의 배수를 다 제거한다.

남아있는 숫자 중(기존에 제거한 숫자는 또 제거할 필요가 없다.) 자기자신을 제외한 3의 배수를 다 제거한다.

남은 수 중에서 1을 제외하고 [2, 3, 5, 7, 11]이 1부터 12사이의 소수가 된다.

에라토스테네스의 체를 사용하면 모든 숫자를 검사할 필요가 없으므로(검사해야하는 범위가 클수록 효과적) 시간 복잡도도 감소한다.

O(N) > O(N^(1/2) )