소수 구하기

프로젝트 오일러 문제들을 풀다보니 소수에 관련된 문제가 많이 나왔다.

처음 소수 구하는 알고리즘을 생각할 당시, 관련 지식이 미비해(공부한 지 너무 오래돼서) 구현한 알고리즘이 너무 조잡했다. (속도가 너무 느렸다.)

오늘 다시 차근차근 검색해 가며 다시 짜봤다.

가장 기초적인 방법

1은 소수가 아니다.

2부터 자신의 수 이전까지 나눠서 떨어진다면 소수가 아니다. (소수는 1과 자신 외에 나눠지면 안된다.)

예 ) 15가 소수인지 판단하려면

15를 2로 나눠 나머지가 0인지 판단. 아니면 15를 3으로 나눠 나머지가 0인지 판단..소수가 아님

씩으로 판별을 하다보니 큰 숫자 (600851475143)가 나온다면 엄청난 계산을 해야 했다.

 

def is_prime(number):
    if number == 1:
        return False

    for i in range(2, number):
        if number % i == 0:
            return False

    return True

나눌 때 절반 까지만 나눔

절반 이상의 숫자들은 확인할 필요가 없는 숫자이기 때문이다.

예를 들어 80이라는 숫자가 있다면, 자기자신을 제외하고 절반을 초과하는 숫자로 나눴을 때 나머지가 0이 되는 숫자가 나올 수가 없기 때문이다.

def is_prime2(number):
    if number < 2:
        return False

    if number == 2:
        return True
    
    if number % 2 == 0:
        return False

    for i in range(3, (number // 2) + 1):
        if number % i == 0:
            return False

    return True

루트까지만 확인

약수의 중심을 구하는 방법이다.

예를 들어 80이라는 숫자가 있다면, 약수들이 1, 2, 4, 5, 8, 10, 16, 20, 40, 80 이 된다.

이것은 1 x 80, 2 x 40, 4 x 20, 5 x 16, 8 x 10, 10 x 8, 16 x 5, 20 x 4, 40 x 2, 80 x 1이 되는 것이다.

이것을 보면 8 이후의 약수들은 8까지의 약수들의 역순(반비례)이다. 이는 80의 제곱근과 엇비슷하다. (80의 제곱근 8.94..........)

따라서 그 이후의 숫자들은 판별할 필요가 없다.

def is_prime3(number):
    if number < 2:
        return False

    if number == 2:
        return True
    
    if number % 2 == 0:
        return False

    for i in range(3, int(number ** 0.5) + 1):
        if number % i == 0:
            return False

    return True

참고사이트

소수(Prime Number) 구하기 효율적 알고리즘 :: 코드자몽

Prime Number(소수) 판별법 알고리즘

Python 제곱과 루트 구하기