[Python] 소수 구하기, 약수 찾기 알고리즘

약수 찾기

소수를 구하려면 약수를 찾는 방법부터 알아야 한다.
소수의 정의는 1과 자기 자신을 약수로 가지는 수, 즉 약수가 2개인 수이기 때문이다.

def is_divisor(n: int, m: int):
    return n % m == 0

n을 m으로 나누었을 때 나머지가 0이면 m이 n의 약수이고, 0이 아니면 m이 n의 약수가 아니다.

소수 구하기

다양한 방법을 소개할 것인데, 아래로 갈 수록 더 간단하고 빠른 코드이다.
간단하고 빠른 코드로 바꾸는 과정을 설명한다.

첫 번째 방법

def is_prime(num: int):
    count = 0  # 약수의 개수
    for i in range(1, num + 1):  # 1 ~ num 사이의 약수 개수 구하기
        if is_divisor(num, i):
            count = count + 1
    return count == 2  # 약수의 개수 2개 == 소수

이 방법은 구하는 시간이 오래 걸린다.
N이 소수인지 알기 위해서 for문을 N번 반복해야 하기 때문이다. (시간복잡도가 N이다.)

구하는 시간을 줄여보자.
첫 번째 방법에서 약수를 찾기 위해 1부터 num까지 하나하나 검사해보았는데,
1부터 $\sqrt{num}$ 까지만 검사해도 된다.

(증명 방법 배웠는데 기억이 안나서 찾으면 올림 ..)

예시를 들어 설명하자면,
16의 약수는 1, 2, 4, 8, 16이다. 16 = 1 x 16 = 2 x 8 = 4 x 4 이므로
1, 2, 4만 구해도 $\sqrt{16}$ (= 4) 보다 큰 약수인 8, 16은 자동으로 구해진다.
1과 16, 2와 8, 4와 4는 각각 한 세트로 생각한다.

이렇게 하면 약수가 1개인 수가 소수이다.
숫자 자기 자신은 검사하지 않기 때문에 약수가 1만 나온다.

두 번째 방법

def is_prime_up_to_root(num: int):
    if num == 1:  # 1은 소수 아님
        return False
    count = 0
    i = 1
    while i * i <= num:  # 1 ~ 루트 num 사이의 약수 개수 구하기
                         # 실수가 나오지 않도록 양변을 제곱하여 식을 변형함
        if is_divisor(num, i):
            count = count + 1
        i = i + 1
    return count == 1

구하는 시간을 더 줄여보자.
처음부터 2의 배수를 제외하는 것이다.
그렇다면 구하는 시간이 절반으로 줄어든다.

세 번째 방법

def is_prime_up_to_root_out_mult2(num: int):
    if num == 1:
        return False
    if num % 2 == 0:  # 2의 배수 제외
        return num == 2  # 2만 소수
    count = 0
    i = 1
    while i * i <= num:
        if is_divisor(num, i):
            count = count + 1
        i = i + 1
    return count == 1

3의 배수도 생략하면 시간이 더더 줄어든다.

코드를 더 간단하게 정리해보자.

네 번째 방법

def is_prime_up_to_root_out_mult2_2(num: int):
    if num % 2 == 0: 
        return num == 2 
    if num % 3 == 0:
        return num == 3
    i = 5  # 1은 나머지가 무조건 0이기 때문에 제외, 2, 3, 4는 위에서 판별
    while i * i <= num:
        if num % i == 0:  # num이 i를 약수로 가짐
            return False
        i = i + 2  # i가 짝수일 때 num이 i를 약수로 가지면 num은 짝수라서 이미 판별
    return num != 1  # 1은 소수 아님

이 방법은 약수를 찾는 함수가 필요 없다.
또한 1을 제외한 다른 약수가 구해지면 num을 바로 합성수라고 판단하고
return False가 실행되어 구하는 시간이 줄어든다.

이 외에도 코드를 더 간단하고 빠르게 만드는 방법이 존재할 수 있다.

소수 출력

소수 구하는 함수를 실행시키는 방법이다.

number = 1
while True:  # 계속 반복함
    if is_prime(number):
        print(number)
    number = number + 1