[BOJ] 1929 : 소수 구하기 [정수론](Python)(feat. 에라토스테네스의 체)

문제 링크

https://www.acmicpc.net/problem/1929

1929번: 소수 구하기

소스 코드

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

sosu = [1 for _ in range(n+1)]
sosu[1] = 0

for num in range(2,int(n**0.5)+1):
    if sosu[num]: # 배수로 제거되지 않은 숫자인 경우
        # 이 숫자의 배수는 전부 0으로 바꿔준다
        for multiple in range(num+num,n+1,num):
            sosu[multiple] = 0

# 배수가 아니라서 1로 남아있던 숫자를 모두 출력
for idx in range(m,n+1):
    if sosu[idx]: print(idx)

 

해설

• 에라토스테네스의 체

사실 어떤 숫자가 소수인지 아닌지 판단하는 것은 아주 간단합니다.

소수란 그 숫자를 나눌 때 1과 자기 자신으로만 나눠 떨어지는 숫자를 뜻하죠.

따라서 2부터 자기 자신-1 까지의 숫자들로 모두 나눠보면서 나머지가 0이 아닌 경우가 있는지 없는지 확인하면 됩니다.

2중 for문으로 코드를 짤 수 있다는 뜻입니다.

(아래는 아주 기초적인 소수 찾기 문제 링크입니다)

https://www.acmicpc.net/problem/1978

1978번: 소수 찾기

 

하지만 이번 문제는 그렇게 간단하지 않습니다.

문제의 조건을 살펴볼까요?

1 ≤ M ≤ N ≤ 1,000,000 입니다.

 

최악의 경우 M = N = 1,000,000이 될 수 있습니다.

이럴 때는 이중 for문을 사용하면 시간복잡도가 최악이 되겠죠?

간단히만 생각해도.. 2부터 백만까지 for문을 돌면서 각 케이스에 또 for문을 더한다?

정확한 계산은 아닙니다만 '백만 x 백만' 이 얼마나 큰 숫자일지 상상해보시기 바랍니다 😂

(백만이라는 숫자에 100만 곱해도 1억입니다..!)

 

결국 우리는 각 숫자를 매번 확인하는 것이 불가능하다는 결론을 내릴 수 있게 됐습니다.

그러면 어떻게 해야할까요? 🤨

 

반대로 생각해보겠습니다.

소수의 정의가 어떤 것으로 나누어도(1과 자기 자신만 빼구요) 나머지가 0이 아니라는 것이라면..어떤 숫자의 배수를 모조리 후보에서 제외하는 것은 어떨까요?

 

예를 들어 10 이하의 소수를 구해봅시다.후보는 [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] 입니다.맨 처음 언급했던 것처럼 1과 10은 고려 대상이 아닙니다(소수의 정의!)우리는 2부터 9까지의 숫자를 살펴볼 거에요!

 

1) 2는 소수입니다.하지만 2의 배수도 소수일까요? 당연히 아니겠죠 😀그러니까 우리는 2를 제외한 2의 배수를 후보 리스트에서 지울 것입니다.따라서 [2, 3, 4, 5, 6, 7, 8, 9] 가 됩니다.

 

2) 3은 소수입니다.아직 지워지지 않았잖아요?이제 생각해보면 3의 배수를 또 지워주면 되겠네요!따라서 남은 후보는 [2, 3, 4, 5, 6, 7, 8, 9] 가 됩니다.

 

3) 4는 이미 지워졌으니까 5를 볼까요?5 역시 어떤 수의 배수가 아니여서 그대로 남아 있는데요, 후보 리스트에 배수가 없습니다..!그래서 후보 리스트는 그대로 유지됩니다.

 

4) 6은 지워졌으니 패스하고.. 7도 소수겠네요.하지만 이보다 더 작은 숫자 5의 배수도 없는 마당에 7의 배수가 존재할리 없죠.따라서 리스트는 그대로 남고 마무리 됩니다.(이후 8, 9는 이미 후보리스트에서 제외됐습니다!)

 

지금까지 내용을 정리하면..

숫자를 하나씩 확인하면서 배수를 모조리 지워준다!

라고 할 수 있습니다.

 

 

이번엔 다른 관점에서 생각해보겠습니다.

사실 말하고 싶은 건.. "모든 숫자를 다 확인할 필요조차 없다"는 것입니다.

만약 우리가 확인하고 싶은 숫자가 n까지의 숫자라면, 우리는 사실 루트 n(n의 제곱근)까지만 봐도 상관 없습니다.

무슨 말이냐면 위의 예시에서 사실 숫자 2와 3의 배수만 지우고 결과를 보면 된다는 뜻입니다.

어떻게 그걸 확신할 수 있을까요?

 

이 사진은 1부터 17까지의 숫자들의 약수를 구한 것입니다.

초록색은 소수, 파란색 원은 제곱수의 제곱근입니다.

그렇다면 빨간색은 무엇일까요?

 

제곱수 4와 9 사이에는 5,6,7,8이 존재하고 5,7은 소수 6,8은 약수가 있는 수입니다.

6을 먼저 보면 6이 소수인지 아닌지 알기 위해서 2로 나눠봤을 때 확인이 끝납니다.

마찬가지로 8도 2로 나누면 소수가 아니라는 것을 알 수 있죠.

 

제곱수 9와 16 사이의 소수가 아닌 숫자, 즉 약수가 존재하는 숫자는 10, 12, 14, 15 입니다.

10은 2로 나누면 확인이 끝나고, 12 역시 2로 나누면 끝납니다.

14 역시 2로 나누면 확인이 끝나고 15는 3으로 나누면 끝납니다.

 

이를 일반화하면 다음과 같습니다.

n^2부터 (n+1)^2 사이의 소수 반별 유무는 "n까지"만 확인해도 충분하다.

즉 4에서 8은 2까지만, 9에서 15는 3까지만, 16부터 24까지는 4까지만 확인하면 된다는 것입니다.

이는 제곱수의 약수쌍이 홀수 대칭이기 때문입니다.

 

소수를 제외하고 4, 6, 8, 9, 10을 보면

4 = 1 2 4

6 = 1 2 3 6

8 = 1 2 4 8

9 = 1 3 9

10 = 1 2 5 10

으로 약수가 구성되어 있는데요, 이때 제곱수가 아닌 수들은 약수의 개수가 짝수입니다.

어떤 수가 n = a * b 라고 할 때 우리는 a * b = b * a 라는 것을 알기 때문에 약수 조합의 절반만 봐도 됩니다.

예를 들어 8 = 1 2 4 8 의 경우 2까지만 봐도 8까지에 대한 판단이 끝난다는 것이죠.

 

하지만 n = a * a 가 될 때는 중간 지점이 곧 a 이므로 여기가 경계가 되어 범위가 증가하게 되는 것입니다.

다시 정리하자면 어떤 수가 소수인지 아닌지 판단하기 위해서 '배수 개념(약수의 배수를 제거)을 적용하는데, 이때 루트 n까지의 범위만 봐도 충분하다'는 것입니다.

(왜 n의 제곱까지만 봐도 충분한건지 최대한 납득이 가도록 설명하고자 노력했는데 쉽지 않네요 😭)