캐시를 이용해 빠르게 소수 판별하기

이 글의 내용 중에는, 2의 배수는 제외하고 나머지 연산을 수행하여 최적화를 하는 방법을 소개하고 있습니다. 저는 여기서 좀 더 확장을 해 보겠습니다.

우선 왜 2의 배수를 제외하고 나머지 연산을 하면 더 빨라지는지를 생각해 봅시다. 조금만 생각해 보면 그 이유를 알 수 있는데, 2로 나누어 떨어지지 않는 수는 2의 배수로도 나누어 떨어지지 않기 때문에, 2가 아닌 2의 배수에 대해서는 나머지 연산을 할 필요가 없는 것입니다.

자 이제 2가 아닌 3으로 생각해 봅시다. 3 역시 3으로 나누어 떨어지지 않는 수는 3의 배수로도 나누어 떨어지지 않습니다. 이것을 일반화 시키면, 어떤 소수 p가 있을 때 p로 나누어 떨어지지 않는 수는 p의 배수로도 나누어 떨어지지 않는다 라고 할 수 있겠습니다.

이것을 이용한 알고리즘을 "에라토스테네스의 체" 라고 합니다.

에라토스테네스의 체 - 위키백과

이 알고리즘을 사용하면, 어떤 자연수 n이 소수인지를 판별할 때 n^0.5(n의 제곱근, 왜 n의 제곱근 이하의 수만 나눠보면 되는지는 첫 링크의 열심히해보자 님의 글에서 설명하고 있습니다) 이하의 소수들로만 나누어 떨어지지 않는지 검사하면 되기 때문에, 기존의 알고리즘(n^0.5이하의 소수 및 합성수 모두로 나누어 보는 방식)에 비해 훨씬 빠르게 소수 판별이 가능합니다.

그런데 여기서 문제가 발생합니다. 이 알고리즘을 사용하여 어떤 자연수 n이 합성수인지 소수인지 알아보려면 최소한 n^0.5(n의 제곱근) 이하의 소수를 모두 알고 있어야 합니다. 우리가 필요한 건 n이 소수인지 아닌지 인데 이것을 알기 위해 n^0.5 이하의 모든 소수를 구해야 합니다. 배보다 배꼽이 커지는 것이죠.

반대로 말하면 n^0.5 이하의 소수를 미리 알고 있다면, 빠르게 소수를 판별할 수 있다는 뜻이 됩니다. 이럴 때 사용하는 것이 캐시 입니다. 처음에 미리 n^0.5 이하의 소수를 모두 구해놓고 그것을 어떤 공간에 저장을 해두는 것입니다. 그러면 n 이하의 수가 소수인지를 판별할 때에는 n^0.5이하의 소수들을 구하지 않고 캐시된 데이터를 사용하여 빠르게 소수 판별을 할 수 있을 것입니다. 그래서 저는 다음과 같은 코드를 작성해 보았습니다(최적화의 여지가 좀 더 남아있긴 하지만, 지금 글에서 중요한 부분은 아니니 넘어가도록 합시다).

// 중복된 코드들을 함수로 묶으면 더 좋겠지만 우선
// 편하게 보기 위해서 하나의 함수로 작성했습니다.
bool IsPrime1(uint64_t n)
{
// 캐시된 데이터(소수)들을 담아둘 벡터
static vector<uint64_t> prime_numbers = {2};
// 필요한 소수의 최댓값. 반복해서 계산할 필요가 없으므로
// 딱 한 번만 계산해서 그 결과를 담아두고 활용합니다.
uint64_t last = static_cast<uint64_t>(sqrt(static_cast<double>(n)));
// 만약 소수 판별을 하려는 n이, 캐시된 소수들 중 가장 큰 수보다 작거나 같다면,
// 벡터 내에서의 이분 탐색으로 빠르게 결과를 도출합니다.
if (n <= *prime_numbers.rbegin()) {
return binary_search(prime_numbers.begin(), prime_numbers.end(), n);
}
// 만일 캐시된 소수가 부족하다면 그 이후의 소수를 계산해서,
// 캐시 역할을 하는 벡터에 추가합니다.
for (uint64_t i = *prime_numbers.rbegin() + 1; i <= last; ++i) {
bool is_prime = true;
auto end = prime_numbers.end();
uint64_t inner_last = static_cast<uint64_t>(sqrt(static_cast<double>(i)));
// 캐시에 소수를 추가할 때에도 이미 캐시된 소수들을 활용하면 더 빠르게 계산이 가능합니다.
for (auto it = prime_numbers.begin(); is_prime && it != end && *it <= inner_last; ++it) {
if (!(i % *it)) is_prime = false;
}
if (is_prime) prime_numbers.push_back(i);
}
// 위 과정에서 n^0.5 이하의 소수를 모두 구해 벡터 안에 넣어두었으니,
// 이제 벡터안에 캐시된 소수들을 사용해서 n이 소수인지 판별하면 됩니다.
auto end = prime_numbers.end();
for (auto it = prime_numbers.begin(); it != end && *it <= last; ++it) {
if (!(n % *it)) return false;
}
return n >= 2;
}

소수 판별 예제 코드 접기

이러한 캐시를 활용하는 방법에도 문제가 있습니다. 바로 데이터가 캐시되기 전에는 n의 소수 여부를 판별하는 작업은 물론이고 캐시할 데이터(소수)를 구하는 작업까지 해야 되기 때문에 많은 시간이 걸린다는 것입니다.

따라서 소수를 딱 한 번 내지 손에 꼽을 정도로 적은 횟수만 판별하는 경우에는 오히려 캐시된 데이터를 구하는 데 시간이 낭비될 수 있습니다. 즉 캐시 방식이 효과를 보려면, 소수를 판별하는 횟수가 많아야 합니다. 이는 바로 다음에 보여드릴, 수행 시간 측정 결과에서도 확인할 수 있습니다.

비교할 함수들은 열심히해보자 님의 글에서 가져왔습니다. 우선 테스트를 위한 소스코드는 다음과 같습니다.

#include <cmath>
#include <cstdint>
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
#include "blc/test/blc_test.h"
using namespace blc;
using namespace blc::test;
// 중복된 코드들을 함수로 묶으면 더 좋겠지만 우선
// 편하게 보기 위해서 하나의 함수로 작성했습니다.
bool IsPrime1(uint64_t n)
{
// 캐시된 데이터(소수)들을 담아둘 벡터
static vector<uint64_t> prime_numbers = {2};
// 필요한 소수의 최댓값. 반복해서 계산할 필요가 없으므로
// 딱 한 번만 계산해서 그 결과를 담아두고 활용합니다.
uint64_t last = static_cast<uint64_t>(sqrt(static_cast<double>(n)));
// 만약 소수 판별을 하려는 n이, 캐시된 소수들 중 가장 큰 수보다 작거나 같다면,
// 벡터 내에서의 이분 탐색으로 빠르게 결과를 도출합니다.
if (n <= *prime_numbers.rbegin()) {
return binary_search(prime_numbers.begin(), prime_numbers.end(), n);
}
// 만일 캐시된 소수가 부족하다면 그 이후의 소수를 계산해서,
// 캐시 역할을 하는 벡터에 추가합니다.
for (uint64_t i = *prime_numbers.rbegin() + 1; i <= last; ++i) {
bool is_prime = true;
auto end = prime_numbers.end();
uint64_t inner_last = static_cast<uint64_t>(sqrt(static_cast<double>(i)));
// 캐시에 소수를 추가할 때에도 이미 캐시된 소수들을 활용하면 더 빠르게 계산이 가능합니다.
for (auto it = prime_numbers.begin(); is_prime && it != end && *it <= inner_last; ++it) {
if (!(i % *it)) is_prime = false;
}
if (is_prime) prime_numbers.push_back(i);
}
// 위 과정에서 n^0.5 이하의 소수를 모두 구해 벡터 안에 넣어두었으니,
// 이제 벡터안에 캐시된 소수들을 사용해서 n이 소수인지 판별하면 됩니다.
auto end = prime_numbers.end();
for (auto it = prime_numbers.begin(); it != end && *it <= last; ++it) {
if (!(n % *it)) return false;
}
return n >= 2;
}
// 가장 기본적인 알고리즘
bool findPrime(uint64_t n)
{
uint64_t i;
for(i = 2; i < n; ++i)
{
if(n % i == 0)
{
return false;
}
}
return true;
}
// n의 제곱근까지만 나누도록 최적화
bool isPrime(uint64_t n)
{
uint64_t i;
for(i = 2; i * i <= n; ++i)
{
if(n % i == 0)
{
return false;
}
}
return true;
}
// 2의 배수를 제외하고, n의 제곱근까지만 나누도록 최적화
bool findPrime1(uint64_t n)
{
uint64_t i;
if(n < 2) return false;
else if(n == 2) return true;
for(i = 3; i * i <= n; i += 2)
{
if(n % i == 0)
{
return false;
}
}
return true;
}
// UnitTest는 제가 만들고 있는 유닛 테스트 도구입니다.
// 차후 정리되면 공개하도록 하겠습니다.
class PrimeTest final : public UnitTest
{
public:
static constexpr uint64_t big_prime = 1'000'000'000'121; // 13자리 소수
PrimeTest() : UnitTest(u8"소수 판별 테스트") {
// 가장 기본적인 알고리즘은 시간이 너무 많이 걸리기도 하고
// 별로 비교하는 의미도 없을 것 같아서 테스트에서 제외했습니다.
Test(u8"findPrime: 가장 기본적인 알고리즘",
[]() {
ASSERT_EQUALS(true, findPrime(big_prime));
}, true // 이 인자가 true면 테스트에서 무시됨(디폴트인자: false).
);
Test(u8"isPrime: n의 제곱근까지만 나누도록 최적화",
[]() {
ASSERT_EQUALS(true, isPrime(big_prime));
}
);
Test(u8"findPrime1: 2의 배수를 제외하고, n의 제곱근까지만 나누도록 최적화",
[]() {
ASSERT_EQUALS(true, findPrime1(big_prime));
}
);
Test(u8"IsPrime1: 캐시를 사용하는 알고리즘(캐시되기전)",
[]() {
ASSERT_EQUALS(true, IsPrime1(big_prime));
}
);
Test(u8"IsPrime1: 캐시를 사용하는 알고리즘(캐시된후)",
[]() {
ASSERT_EQUALS(true, IsPrime1(big_prime));
}
);
}
} prime_test;
int main()
{
// 테스트 결과를 HTML파일로 출력
return UnitTest::Run("A:\\prime_test.html");
}

소수 판별 예제 코드 접기

참고로 i^2와 n을 비교하는 방법이 있고 i와 n^0.5를 비교하는 방법이 있는데 이 둘 역시 각각의 장단점이 있습니다. 비록 i^2이 n^0.5보다는 매우 값싼 연산이지만 반복문의 반복 횟수가 엄청나게 많다면, 딱 한 번만 계산해도 되는 n^0.5와 i를 비교하는게 더 싸게 먹힐 수 있습니다. 반대로 반복문의 반복 횟수가 그리 많지 않다면 i^2를 반복문의 반복 횟수만큼 계산하는 것이 n^0.5를 한 번 계산하는 것보다 싸게 먹힐 수 있습니다. 따라서 이런 류의 최적화를 할 때에는 실제로 자신이 만드는 프로그램의 특성을 잘 파악할 필요가 있습니다.

이제 테스트 결과를 보도록 합시다.

테스트 결과를 통해 캐시 벡터를 만드는데 엄청난 시간이 드는 것을 볼 수 있습니다. 대신 캐시 벡터가 만들어진 후에는 기존의 알고리즘보다 빠른 속도로 소수 여부를 판별 할 수 있습니다.

따라서 캐시를 활용하는 알고리즘이 이득을 보려면 프로그램에서 소수를 판별할 일이 매우 많아야 한다는 것을 알 수 있습니다. 만일 소수를 판별할 일이 그다지 많지 않다면 열심히해보자 님이 작성하신 코드처럼, 2의 배수를 제외하고, n의 제곱근까지만 나머지를 구하는 코드가 훨씬 더 효율적일 것입니다.