소수를 빠르게 찾는 방법

6k ± 1 최적화 방법은 소수를 찾기 위한 알고리즘에서 매우 유용한 테크닉이다. 이 방법은 모든 소수가 6의 배수 양 옆 혹은 6의 배수를 제외한 6k ± 1 형태로 존재한다는 관찰에 기반한다.

#수학적 배경

6의 배수를 생각해보면, 6k(k는 자연수)는 항상 2와 3의 공배수다. 따라서 소수는 6k에서 발생할 수 없다. 이제 6k 주변을 살펴보면 다음과 같은 형태를 갖게 된다.

• 6k - 2 = 2(3k - 1) : 2의 배수
• 6k - 3 = 3(2k - 1) : 3의 배수
• 6k : 2와 3의 공배수
• 6k + 2 = 2(3k + 1) : 2의 배수
• 6k + 3 = 3(2k + 1) : 3의 배수

위에서 보듯, 6k - 2, 6k - 3, 6k + 2, 6k + 3 모두 2 또는 3의 배수이기 때문에 소수가 발견될 수 없다. 결과적으로 6의 배수가 아닌 수 중에서 소수를 찾을 가능성이 있는 것은 오직 6k - 1과 6k + 1 뿐이다. 이 두 형태는 6의 배수를 기준으로 앞뒤에 위치하며, 2나 3의 배수가 아닌 경우에 소수일 가능성이 있다.

#알고리즘 구현

이 관찰을 통해 소수 판별 함수나 에라토스테네스의 체 알고리즘을 최적화할 수 있다. 일반적으로 소수 판별 시에 모든 수를 확인하는 대신, 6k ± 1 형태에 해당하는 수들만 검사하면 계산량을 줄일 수 있다. 다음은 6k ± 1 최적화를 포함한 C++ 소수 판별 함수다.

#include <cmath>

bool isPrime(int n) {
    if (n <= 1) return false; // 1 이하는 소수가 아님
    if (n <= 3) return true;  // 2와 3은 소수
    if (n % 2 == 0 || n % 3 == 0) return false; // 2 또는 3으로 나누어 떨어지면 소수가 아님
    for (int i = 5; i * i <= n; i += 6) {
        if (n % i == 0 || n % (i + 2) == 0) return false; // 6k - 1 및 6k + 1 형태 검사
    }
    return true;
}

#성능 향상

이 최적화 방법은 소수를 찾는 알고리즘의 효율을 상당히 향상시킨다. 특히 큰 숫자를 대상으로 할 때, 6의 배수에 대한 배제로 인해 필요한 계산량을 대폭 줄일 수 있다. 그러나 이 방법이 소수를 찾는 데 필요한 모든 계산을 제거하는 것은 아니며, 6k ± 1 형태의 수들 중에서도 실제로 소수가 아닌 경우가 많기 때문에 추가적인 검증이 필요하다.