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

문제

나의 답안

m,n=map(int,input().split())

for i in range(m,n+1):
    if i==1:#1은 소수가 아니므로 제외
        continue
    for j in range(2,int(i**0.5)+1):
        if i%j==0: #약수가 존재하므로 소수가 아님
            break   #더이상 검사할 필요가 없으므로 멈춤
    else:
        print(i)

이 문제는 에라토스테네스의 체로 풀 수 있는 문제이지만,
내가 작성한 코드는 각 수에 대해 제곱근까지만 나눠보며 소수를 판별하는 방식이다.

1. 1은 소수가 아니므로 제외해준다.
2. 반복문을 돌린다. 범위는 2부터 int(i**0.5)+1까지이다. 특정 수의 제곱근을 구해, 그 제곱근까지의 약수를 구하면 해당 약수를 포함하는 수를 모두 제거할 수 있다(소수가 아니기에). 이렇기 때문에 범위를 위와같이 설정해주었다.
   • 예를들어, i=12에서 12의 약수는 1 2 3 4 6 12
     int(sqrt(12))=3이고 12는 3으로 나누어 떨어지므로 더 검사할 필요가 없다.
3. i가 j로 나누어떨어지므로 약수가 존재한다. 고로 소수가 아니고, 해당 제곱근(j)이상의 숫자에 대해 더이상 검사할 필요가 없으므로 멈춘다.
4. i가 1이 아니라면 해당 숫자를 출력해준다.

이 때의 시간복잡도는 O(N^(1/2))이 된다.

에라토스테네스의 체

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

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

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

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

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