[python] 소수 판별 알고리즘

처음 적어보는 벨로그.

소수를 판별하는 방법을
알고리즘으로 구현해보려고 한다.

참고로, 밑의 코드는 함수로 작성하였다.

함수 이름이 긴건 안비밀

1)

가장 기본적인걸로는,
단순히 약수의 개수를 새어서
1과 자기자신만 나오는 경우 (약수가 두개인 경우)를
소수로 판별한다.

def prime_found_divisor(num: int):
    if num == 1:                         # 1은 예외이므로 설정  
    	print("1은 소수도, 합성수도 아님~!")
        return 0                          # 확인했으니까 끝
    count = 0                            # 약수의 개수
    for i in range(1, num + 1):          # 1부터 num까지
        if num % i == 0:                 # num이 i 로 나눠진다면
            count += 1
    if count == 2:                       # 약수가 두개라면
        print("소수!!")
    else:
        print("합성수...")

단순하지만,
숫자가 매우 커진다면 (10의 5제곱만 되어도...)
오래 걸리게 된다. (1부터 num까지 다 나누기 때문에)

2)

짝수는 절대 소수가 될 수 없다.

2를 제외한 짝수는 2를 소인수로 가지기 때문에,
나누는 것이 의미없다.

이렇게 될 경우,
count의 값이 실제 약수의 개수는 아니다.

이 점을 주의하면서,
이를 반영한 코드를 짜보자.

def prime_found_divisor_not_even(num: int):
    if num == 1:                         # 1은 예외이므로 설정  
    	print("1은 소수도, 합성수도 아님~!")
        return 0                          # 확인했으니까 끝
    count = 0  # 약수의 개수
    if num % 2 == 0:                     # for 문에서 2가 제외되기 때문에 따로 판별 
        count += 1
    for i in range(1, num + 2, 2):       # 1부터 num까지 홀수의 경우만 확인
        if num % i == 0:                 # num이 i 로 나눠진다면
            count += 1
    if count == 2:                       # 약수가 두개라면
        print("소수!!")
    else:
        print("합성수...")

숫자가 커지게 될 경우, 1번에 비해 계산하는 시간이 더 적다.

3)

약수의 성질을 살펴보자.

15의 약수를 보자.
1 / 3 / 5 / 15
1 x 15 = 3 x 5 = 15

20의 약수를 보자.
1 / 2 / 4 / 5 / 10 / 20
1 x 20 = 2 x 10 = 4 x 5 = 20

약수의 절반정도만 확인해도 충분히 판별이 가능하다.

그렇다면, 약수의 절반을 계산하는 방법은 어떻게될까?

n x m = num 이라 하면
n이 m보다 클 때, m이 가장 큰 경우를 p라고 해보자.
이때에, p x p <= n x m = num 이 된다.
이때, p의 경우까지 약수를 계산하면 된다.

음... 헷갈릴때는 대입을 해보자.
위에서 예시로 든 20.
m이 가장 큰 경우는(p의 경우) n이 5일때, m이 4일때이다.
(4 x 4 <= 5 x 4 = 20)
이 때의 경우는 1부터 4까지만 확인하게 된다.

이를 참고하여 코드를 짜보자.

def prime_found_divisor_square(num: int):
    if num == 1:                          # 1은 예외이므로 설정  
    	print("1은 소수도, 합성수도 아님~!")
        return 0                          # 확인했으니까 끝
    count = 0                             # 약수의 개수
    i = 1                                 # i는 1부터 시작
    while i * i <= num:                   # 위에서 이야기한 1부터 m까지 확인
        if num % i == 0:                  # num이 i 로 나눠진다면
            count += 1
        i += 1
    if count == 2:                        # 약수가 두개라면
        print("소수!!")
    else:
        print("합성수...")

숫자가 커지게 되면, 1번과 2번에 비해 더 빠르게 계산할 수 있다.

더 있을경우, 추가적으로 작성해보도록 하겠다.