📘[Math] 소수를 구하는 방법에 대해서…

소수 구하는 방법

소수는 1과 자기자신만을 약수로 갖는 2이상의 자연수를 말한다.

2, 3, 5, 7, 11, 13 ...

코딩테스트 문제를 풀다보니, 소수를 구하는 방법이 다양하길래 정리해본다.

그냥 나눠!

첫 번째 방법은 그냥 계속해서 나누어보는 방식이다.
주먹구구식 방법이긴 한데, 나름 괜찮았다.

먼저 수들이 갖는 약수의 특징을 보면, 항상 대칭 구조를 이룬다는 점이다.

8 : 1, 2, 4, 8
25 : 1, 5, 25
62 : 1, 2, 31, 62
...

이 처럼 약수는 대칭 구조를 이루고, 대칭을 이루는 그 기준은 제곱근이다.
주어진 수의 제곱근을 기준으로 살펴보자.
n = p * q로 생각했을 때, p와 q중 한 수는 항상 \(\sqrt{n}\) 이하, 한 수는 항상 \(\sqrt{n}\) 이상이다.

이걸 적용해서 코드로 작성해보면 다음과 같다.

def is_prime(n):
    for i in range(2, int(math.sqrt(n)) + 1):
        if n % i == 0:
            return False
    return True

반복하는 일이 많은 경우에는 int(math.sqrt(n))을 for문의 조건식에 넣게되면 계속해서 제곱근을 구하는 동작이 필요하므로, m = int(math.sqrt(n)) 처럼 변수로 빼서 사용하면 좋다고 한다.

에라토스테네스의 체

프로그래밍 대회에서 자주 사용되는 방식이라고 한다.
에라토스테네스의 체 알고리즘의 방식은 나무위키에서 확인했다.
알고리즘은 다음과 같다.

1. 구하고자 하는 소수를 2부터 나열한다.
2. 2는 소수이므로 빼놓고, 2를 제외한 2의 배수를 모두 지운다.
3. 3은 소수이므로 빼놓고, 3을 제외한 3의 배수를 모두 지운다.
4. 4는 2번과정에서 이미 지워졌으므로 건너뛴다.
5. 5는 소수이므로 빼놓고, 5를 제외한 5의 배수를 모두 지운다.
6. 7은 소수이므로 빼놓고, 7을 제외한 7의 배수를 모두 지운다.
7. 위 과정을 구간 내에서 계속해서 반복하면, 구간 내의 모든 소수가 남는다.

이 과정을 코드로 구현하면 다음과 같다.

def eratos(n):
    # 처음 모든 수를 소수라고 가정한다. 어차피 지워갈거니까.
    arr = [1 for i in range(n + 1)]
    
    if n <= 1:
        return False
    else:
        for i in range(2, n):
            if arr[i]:
                for j in range(i + i, n, i): # i의 배수를 지우기 위해 i만큼 증가(i + i 대신 i * 2도 가능)
                    arr[j] = False
        return [i for i in range(2, n) if arr[i]]

여기서 for j in range(i + i, n, i)가 가장 이해가 안되는 부분이었다.
그래서 직접 코드로 작성하고, 여러 케이스들을 바꿔가면서 확인했다.
생각이 중간에 꼬였었던거였다.
예를 들면, 3은 소수니까 3을 제외한 3의 배수를 지워야하는거니까, 3의 배수 중 가장 작은 수인 3 * 2 == 3 + 3부터 시작하는게 맞았다.
증가폭은 배수를 찾아야하니 당연히 i만큼 증가하는게 맞다.

참고자료

[https://ko.wikipedia.org/wiki/%EC%97%90%EB%9D%BC%ED%86%A0%EC%8A%A4%ED%85%8C%EB%84%A4%EC%8A%A4%EC%9D%98%EC%B2%B4](https://ko.wikipedia.org/wiki/%EC%97%90%EB%9D%BC%ED%86%A0%EC%8A%A4%ED%85%8C%EB%84%A4%EC%8A%A4%EC%9D%98%EC%B2%B4)