티스토리 뷰
소수는 1과 자기 자신을 제외하고는 어떠한 수로도 딱 나눠지지 않는 수를 의미합니다. 위키피디아에서는 다음과 같이 설명합니다 :
자신보다 작은 두 개의 자연수를 곱하여 만들 수 없는 1보다 큰 자연수이다. 예를 들어, 5는 1 x 5 또는 5 x 1로 수를 곱한 결과를 적는 유일한 방법이 그 수 자신을 포함하기 때문에 5는 소수이다. 그러나 6은 자신보다 작은 두 숫자(2 × 3)의 곱이므로 소수가 아닌데, 이렇듯 1보다 큰 자연수 중 소수가 아닌 것은 합성수 라고 한다. 1과 그 수 자신 이외의 자연수로는 나눌 수 없는 자연수로 정의하기도 한다.
알고리즘 사이트에서는 소수를 주제로 한 알고리즘 문제가 많이 존재합니다. 이번 포스팅에서는 그 중, 소수를 생성하는 알고리즘에 대해서 알아보도록 하겠습니다.
에라토스테네스의 체(Sieve of Eratosthenes)
에라토스테네스의 체는 소수를 찾는 알고리즘 중에서 가장 널리 알려져 있는 소수 생성 알고리즘입니다. 굉장히 직관적이고, 구현하기가 쉽습니다. 위키피디아에서는 에라토스테네스의 체를 다음과 같이 정의합니다 :
에라토스테네스의 체 는 주어진 한계까지 모든 소수를 찾는 간단한 고대의 알고리즘이다. 첫 번째 소수 2로 시작하여 각 소수의 배수를 합성수(소수가 아님)로 표시하는 방식으로 동작한다. 이것은 시험 분할을 사용해 각각의 후보 수(candidate number)를 각각의 소수로 나눌 수 있는지 순차적으로 테스트하는 방식과 체의 주요 차이점이다.
그림으로 보시면 바로 감이 오시리라 생각합니다.
앞선 인용에서 시험 분할과 체의 방식이 다르다고 언급되어 있는데, 설명을 첨가하자면 시험 분할(trial division)이라는 것은 임의의 정수 N에 대해서 N보다 작은 수로 N을 나눌 수 있는지 테스트 하는 방법을 의미합니다. 만약 N = 12라면, N보다 작은수(1 ~ 11)이 될 수 있습니다. 이 시험 분할로 둘 이상의 인자가 발견되면 이 수는 합성수(composite number)로 판정나게 됩니다. 이 이야기에 대한 자세한 사항은 해당 링크를 참조하시기 바랍니다.
구현
에라토스테네스의 체의 구현은 다음과 같습니다 :
#include <iostream>
#include <cstring>
#include <cmath>
using namespace std;
int main()
{
/* 에라토스테네스의 체를 실행할 구간 */
unsigned int Limit;
cin >> Limit;
/* 소수인지 아닌지를 저장하기 위한 배열 */
bool* IsPrimes = new bool[Limit];
memset(IsPrimes, true, sizeof(bool) * Limit);
IsPrimes[0] = false;
IsPrimes[1] = false;
/* 에라토스테네스의 체 */
for (unsigned int i = 2; i <= sqrt(Limit); ++i)
{
/* 현재 수가 소수이면 배수들을 전부 합성수로 표기합니다. */
if (IsPrimes[i] == true)
{
for (unsigned int j = i * 2; j < Limit; j = j + i)
{
IsPrimes[j] = false;
}
}
}
return 0;
}첫 번째 반복문에서 Limit까지가 아닌 제곱근까지만 순회하는 이유는 약수의 특징에서 근거한 것입니다. 임의의 정수 N에 대한 약수의 절반은 1 ~ sqrt(N) 범위에 존재합니다. 나머지 절반은 sqrt(N) + 1 ~ N 범위에 존재한다는 의미입니다. 이것을 응용하면 소수를 판단할 때 2 ~ sqrt(N)까지만 검사하면 소수인지 아닌지를 판별할 수 있게 됩니다.
또한 위 코드에서는 구현되어 있지 않지만, 2를 제외한 모든 소수가 홀수인 점을 착안해 증가값을 2로 설정하여 홀수만 순회하도록 하여 성능을 올릴 수 있습니다.
이 알고리즘의 복잡도는 임의 접근 기계(random access machine) 모델에서 O(n log log n)이라고 합니다.
오일러의 체(Sieve of Euler)
에라토스테네스의 체는 일부 합성수들이 두 번 이상 처리되어야 한다는 점에서 비효율적인 연산이 존재합니다. 가령, 42의 경우 2, 3, 7로 소인수분해할 수 있으며 따라서 에라토스테네스의 체에서 3번이나 걸러집니다. 오일러의 체는 Euler가 추가적인 비용으로 각 합성수들을 정확히 한 번만 거르는 체를 발명했습니다.
오일러의 체는 다음과 같이 동작합니다 :
- 2부터 n까지의 리스트를 만듭니다.
- 리스트에서 첫 번째 숫자를 추출하고 첫 번째 숫자를 포함하여 원래 목록의 각 요소에 추출된 첫 번째 숫자를 곱한 새 리스트를 만듭니다.
- 원본 리스트에서 새 리스트에 나타나지 않는 숫자만 유지하고 중복되는 리스트는 제거합니다.
- 목록에서 첫 번째 숫자를 소수로 출력하고 첫 번째 요소를 제외한 후, 위 과정을 반복합니다.
예시를 들자면 다음과 같습니다. 2 ~ 30까지 리스트가 있을 때, 새 리스트는 4, 6, 8 ... 60이 됩니다. 원본 리스트에서 새 리스트를 빼면 2, 3, 5, 7 ... 29가 리스트가 됩니다. 이것이 첫 루프입니다. 이후, 2를 제외하고 만든 새 리스트는 9, 15, 21 ... , 87이며, 원본에서 새 리스트를 빼면 3, 5, 7, 11, 13 ... 29가 됩니다. 이것이 반복됩니다.
[추가] : O(n)의 시간복잡도를 가지는 에라토스테네스의 체에 대한 알고리즘이 해당 사이트에 올라와 있습니다. 참고하시기 바랍니다.
구현
오일러의 체 구현 코드는 다음과 같습니다 :
#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>
using namespace std;
int main()
{
/* 체의 한계지점 */
unsigned int Limit;
cin >> Limit;
/* 원본 숫자 리스트 */
vector<int> OriginalList;
OriginalList.reserve(Limit);
for (unsigned int i = 2; i < Limit; ++i)
{
OriginalList.push_back(i);
}
/* 소수를 저장할 컨테이너 */
vector<int> Primes;
/* 오일러의 체 */
while (OriginalList.size() > 0)
{
/* 원본 리스트의 0번째 인덱스 * 모든 엘리먼트의 값을 새 리스트에 등록 */
vector<int> NewList;
NewList.reserve(OriginalList.size());
for (const auto& it : OriginalList)
{
NewList.push_back(it * OriginalList[0]);
}
/* 새 리스트의 요소와 중첩되는 원본 리스트 요소들 전부 제거 */
for (auto it = NewList.begin(); it != NewList.end(); )
{
vector<int>::iterator FindIndex = find(OriginalList.begin(), OriginalList.end(), *it);
if (FindIndex != OriginalList.end())
{
OriginalList.erase(FindIndex);
}
else
{
it++;
}
}
/* 원본 리스트의 0번째 인덱스를 소수로 등록하고 리스트에서 제거 */
if (OriginalList.size() > 0)
{
Primes.push_back(OriginalList[0]);
OriginalList.erase(OriginalList.begin());
}
}
/* 소수 출력 */
int Count = 0;
for (const auto& it : Primes)
{
cout << it << "\t";
Count++;
if (Count % 10 == 0)
{
cout << endl;
}
}
return 0;
}오일러의 체에서도 아리스토테네스의 체의 성능 향상을 위해 사용할 수 있는 sqrt 및 홀수 인덱스 증가를 사용할 수 있습니다. 오일러의 체의 경우, 합성수에 대한 중복 연산이 제거됨으로써 시간복잡도가 O(n)이라고 합니다.
순다람의 체(Sieve of Sundaram)
순다람의 체는 1934년에 인도의 수학자 S.P.Sundaram에 의해 발견된 알고리즘입니다. 순다람의 체는 지정된 정수까지 소수를 찾아 올라가는 간단한 결정론적 알고리즘(deterministic algorithm)입니다.
동작 방식은 다음과 같습니다 :
1 ~ N까지의 정수 리스트에 대해 1 <= i <= j이고 i + j + 2ij <= N인 모든 i + j + 2ij 수를 제거하고 남은 수에 대해 2를 곱하고 1을 더해서 2N + 2 이하의 홀수 소수 리스트를 도출합니다.
예를 들어 보겠습니다. N이 10일 때, 위 두 조건식을 만족하는 i, j는 다음과 같이 존재할 수 있습니다:
(1,1) (1,2) (1,3) {(1,4)의 경우 i + j + 2ij = 13이므로 만족하지 못함.}
(2,2) {(2,3)의 경우 i + j + 2ij = 17이므로 만족하지 못함.}
여기서 (1,1)일 때 i + j + 2ij = 4, (1,2) = 7, (1,3) = 10, (2,2) = 10이므로 이 수들을 제거하면 리스트에 1, 2, 3, 5, 6, 8, 9가 남습니다. 이 수들에 대해 2를 곱하고 1을 더하면 3, 5, 7, 11, 13, 17, 19가 됩니다. 여기에 2를 섞어주면 22 이하의 모든 소수를 찾게 됩니다.
이 방식이 동작하는 이유에 대해서는 해당 링크의 Correctness 섹션에서 설명하고 있으니 관심있으신 분들은 참고하시기 바랍니다.
구현
순다람의 체의 구현 코드는 다음과 같습니다 :
#include <iostream>
#include <cstring>
using namespace std;
int main()
{
/* 2N + 2 이하의 소수를 구하기 위한 수 */
unsigned int N;
cin >> N;
/* 소수인지 아닌지 저장하는 배열 */
bool* IsPrimes = new bool[N+1];
memset(IsPrimes, true, sizeof(bool) * (N+1));
/* 순다람의 체 */
for (unsigned int i = 1; 2 * i + 2 * i * i <= N; ++i)
{
int Unary;
for (unsigned int j = i; (Unary = i + j + (2 * i*j)) <= N; ++j)
{
IsPrimes[Unary] = false;
}
}
/* 순다람의 체 출력 */
for (int i = 0; i <= N; ++i)
{
if (i == 0)
{
cout << 2 << " ";
continue;
}
if (IsPrimes[i] == true)
{
cout << 2 * i + 1 << " ";
}
cout << endl;
}
return 0;
}
순다람의 체의 시간복잡도는 O(n log n) 이라고 합니다. 아리스토텔레스의 체보다 이론상 빠르지만, 해당 링크에 따르면, 1억 이하의 소수(5761455)의 계산에 대해 에라토스테네스의 체가 2초가량 더 빠르다고 합니다. 또한 해당 링크에서는 각종 소수 생성 알고리즘의 동작 시간 비교표가 있는데 다양한 소수 생성 알고리즘의 실행 속도를 참고하시기 바랍니다.
[추가] : 스택오버플로우에 따르면, 순다람의 체는 너무 느려서 아무도 사용하지 않는다고 합니다.
앳킨의 체(Sieve of Atkin)
앳킨의 체는 지정된 정수까지 모든 소수를 찾는 현대 알고리즘입니다. 고대의 아리스토테네스의 체와 비교했을 때, 앳킨의 체는 몇 가지 예비 작업을 수행한 다음 소수의 제곱의 배수를 지움으로써, 이론적으로 더 나은 점근적 복잡성(asymptotic complexity)을 달성합니다.
동작방식을 설명하기 전에 알고리즘의 기본 설명은 다음과 같습니다:
- 모든 나머지는 모듈로-60의 나머지입니다 (수를 60으로 나눈 나머지 값)
- x와 y를 포함한 모든 수는 양수입니다.
- 체 리스트 내의 항목을 뒤집는 것(flip)은 마크(소수인지 아닌지, bool로 생각하면 편합니다.)를 반전시키는 것을 의미합니다.
- 이것의 결과가 홀수해인 경우. 해당 방정식에 대해 잠재적 소수(해당 숫자가 제곱이 없는 숫자일 경우, 소수입니다)인 숫자들이며, 짝수해인 경우, 합성수입니다.
동작방식은 다음과 같습니다:
- 결과 리스트(results list)를 생성합니다. 2 3 5를 포함합니다.
- 각 양수에 대한 항목들을 포함한 체 리스트(sieve list)를 생성합니다. 이 리스트의 모든 항목들은 비소수로 마크되어야 합니다(합성수라는 의미).
- 체 리스트 내의 임의의 항목 번호 n 및 은 모듈로-60의 나머지 r에 대해 :
- r이 1, 13, 17, 29, 37, 41, 49, 53일 때 4x^2 + y^2 = n 인 모든 항목 n을 뒤집습니다(flip). 이 단계에서 체의 범위에 대한 플립 연산의 수를 비율로 나타내면 (4√π / 15) x 8 / 60 (분수의 "8"은 이차 방정식과 모듈로 60에 의해 처리된 8개의 모듈로(modulo)를 의미하며, 이는 앳킨(Atkin)이 모듈로 60 wheel 짝수 개를 기준으로 계산했기 때문입니다)이며, 소수로 나타내면 약 0.1117010721276... 이 나옵니다.
- r이 7, 19, 31, 43일 때 3x^2 + y^2 = n 인 모든 항목 n을 뒤집습니다. 이 단계에서 체의 범위에 대한 플립 연산의 수를 비율로 나타내면 π√0.12 x 4 / 60(분수의 "4"는 이차 방정식과 60에 의해 처리되는 4개의 모듈로를 의미하며, 이는 앳킨이 모듈로 60 wheel 짝수 개를 기준으로 계산했기 때문입니다)이며, 소수로 나타내면 약 0.072551974569... 입니다.
- r이 11, 23, 47, 59일 때 3x^2 - y^2 = n 인 모든 항목 n을 뒤집습니다. 이 단계에서 체의 범위에 대한 플립 변산의 수를 비율로 나타내면 √1.92 x ln(√0.5 + √1.5) x 4 / 60(분수의 "4"는 ...(중략))이며, 소수로 나타내면 약 0.060827679704... 입니다.
- r이 이외의 경우일 때, 완전히 무시됩니다.
- 체 리스트에서 가장 낮은 수부터 시작합니다.
- 체 리스트에서 소수로 마크된 다음 숫자를 취합니다.
- 결과 리스트에 숫자를 포함시킵니다.
- 해당 수의 제곱수 및 제곱수의 배수들을 전부 합성수(non-prime)로 마크합니다. 주목할 것은 2, 3, 5에 의해 인수분해 될 수 있는 배수들은 마크되지 않으며, 이는 소수의 마지막 열거 시에 무시될 것이기 때문입니다.
- 4-7번 과정을 반복합니다. 체 범위에 대해 소수들의 제곱들을 마크하는 반복 작업의 총 수를 비율로 표현하면 제곱된 소수의 역수들의 합이며, prime zeta function92) of 0.45224752004... - 1 / 2^2 - 1 / 3^2 - 1 / 5^2에 근접하며(approach) 이 소수들은 범위당 휠 적중률(the ratio of wheel hits per range) 16 / 60에 의해 곱해진 결과에 따라 휠에 의해 제거된 것입니다. 이것은 약 0.01363637571... 의 비율을 나타냅니다.
나름 번역한다고 했지만, 수학적 지식이 미치지 못해 제대로 번역이 되지 않았을 경우가 높습니다. 정확한 내용은 해당 원문의 Algorithm 섹션을 참조하시기 바랍니다.
알고리즘의 설명은 위키피디아에도 있지만 Quora에서 다음과 같이 설명하고 있습니다 :
휠 사용에 대한 아이디어를 살펴보겠습니다. 우리가 2 이후의 짝수가 나오지 않는다는 것을 알고 있음에도 불구하고 체(sieve)는 모든 짝수를 검사하느라 시간을 낭비하고 있음에 주목해야 합니다. 따라서 그것들을 모두 무시합니다 - 짝수를 저장하지 말고, 반복시에 패스합니다. 좀 더 구현에 신경을 쓰면, 이것을 3부터 적용할 수 있습니다. 이것은 마치 매번 2 * 3 = 6(여섯) 숫자마다 반복하는 고정된 점처럼 보이기 때문에 때때로 mod-6 휠이라고 부르기도 합니다. 2/3/5(mod-30) 휠은 빠른 구현에서 일반적이며, 또 2/3/5/7(mod-210) 휠을 사용할 수도 있습니다. (이 아이디어에 설명이 휠 인수분해(wheel factorization)을 의미하는 것 같아 관련 링크를 첨부하여 설명을 보충하셔도 좋을 것 같습니다.)
이제 쉽고 빠르게 지난 합성수들을 스킵하는 체의 아이디어를 이해하기 위해 SoA(아킨의 체)를 설명할 시간입니다. SoA는 mod-60 wheel을 사용하며, 2 * 2 * 3 * 5이므로 mod-30 휠을 사용하는 SoE가 2와 3과 5의 배수들을 스킵하는 방법을 쉽게 알 수 있습니다. 이후, 저자는 mod-60 범위에서 허용 가능한 나머지(2, 3, 5의 배수가 아닌 값들)를 각각 자체 알고리즘을 가진 3개의 그룹으로 나눌 수 있음을 보여줬습니다. 각각의 알고리즘은 특정 2차 방정식( 예를 들어, 4x^2 + y^2 = 60k + delta 같은)을 만족하는 범위의 항목들을 터치하여, q^2의 배수들을 합성수로 표시합니다(즉, 소수의 배수가 아닌 소수의 제곱수의 배수를 합성수로 표기한다는 것을 의미합니다).
위 알고리즘은 그 조건이 유지된다는 것을 증명했습니다(즉, 숫자가 이 방정식들을 충족하면, q^2 수들을 건너뛴다는 것입니다). 또한 이 알고리즘은 점근적 복잡성 mod-30 휠을 사용하는 SoE보다 합리적인 메모리 사용과 함께 약간 더나은 결과를 보여줍니다. Pritchard는 1983년에 동일한 점근적 복잡성을 더 많은 메모리를 사용함으로써 달성하였습니다. Dan Berstein은 더 빠른 구현을 작성하였습니다.
해당 링크에는 SoA와 SoE에 대한 프로그래밍 이슈 역시 설명되어 있으므로 참고하시기 바랍니다.
구현
SoA에는 제가 직접 짜기에는 많은 프로그래밍 이슈가 언급되어 있는 것을 보고 기재되어 있는 코드를 발췌해 왔습니다. 구현 코드는 다음과 같습니다(원본 코드 :
/*
* C++ Program to Implement Sieve of Atkins
*/
#include <iostream>
#include <cmath>
#include <vector>
#define ll long long
using namespace std;
/*
* Sieve of Atkins
*/
void sieve_atkins(ll int n)
{
vector<bool> is_prime(n + 1);
is_prime[2] = true;
is_prime[3] = true;
for (ll int i = 5; i <= n; i++)
{
is_prime[i] = false;
}
ll int lim = ceil(sqrt(n));
for (ll int x = 1; x <= lim; x++)
{
for (ll int y = 1; y <= lim; y++)
{
ll int num = (4 * x * x + y * y);
if (num <= n && (num % 12 == 1 || num % 12 == 5))
{
is_prime[num] = true;
}
num = (3 * x * x + y * y);
if (num <= n && (num % 12 == 7))
{
is_prime[num] = true;
}
if (x > y)
{
num = (3 * x * x - y * y);
if (num <= n && (num % 12 == 11))
{
is_prime[num] = true;
}
}
}
}
for (ll int i = 5; i <= lim; i++)
{
if (is_prime[i])
{
for (ll int j = i * i; j <= n; j += i)
{
is_prime[j] = false;
}
}
}
for (ll int i = 2; i <= n; i++)
{
if (is_prime[i])
{
cout<<i<<"\t";
}
}
}
/*
* Main
*/
int main()
{
ll int n;
n = 300;
cout<<"Following are the prime numbers below "<<n<<endl;
sieve_atkins(n);
cout<<endl;
return 0;
}
앳킨의 체의 시간복잡도는 O(N / loglog N) 이라고 합니다(산술 복잡도 뿐만이 아니라 비트 복잡도 역시). 위키피디아에 따르면 "알고리즘의 점근 시간 복잡성을 감소 시켰다고 해서 점근 시간 복잡도가 더 큰 알고리즘보다 실제 구현이 더 빨리 실행되는 것은 아닙니다. 점근 복잡도가 작을수록 개별 연산에는 시간 복잡성이 증가하는 상수 요인이 있습니다." 라고 하니 참고하시기 바랍니다.
스택오버플로우에 따르면, 앳킨의 체는 O(n) 시간복잡도를 가지는 변형된 SoE보다 느리게 실행된다고 합니다.
결론
곱셈 알고리즘이라던가, 기타 알고리즘처럼 구현 난이도가 증가할수록, 실행 복잡도가 확연히 달라지던 것과 달리 소수 생성 알고리즘은 최적화된(optimized) 에라토스테네스의 체가 실행 시간에서 가장 빠른 속도를 보여준다고 합니다. 언젠가는 변형된 순다람의 체 알고리즘 또는 앳킨의 체 알고리즘이 등장하여 이를 대체할 수 있으리라 생각합니다.
레퍼런스
위키피디아 - 소수(수론)
위키피디아 - Sieve of Eratosthenes
Geeksforgeeks - Sieve of Eratosthenes in O(n) time complexity
Programmingpraxis - Sieve of Euler
위키피디아 - Sieve of Sumdaram
Wordpress - The Sieve of Sundaram
오현석(Frank)의 블로그 - 고차 프로그래밍과 타입 추론 연습문제 풀이
Hashcode - N이하의 소수를 나열하는 가장 빠른 방법
StackOverflow - fastest way to list all primes below n
위키피디아 - Sieve of Atkin
Geeksforgeeks - Sieve of Atkin
Quora - How can sieve of Atkin be explained in simple terms
Sanfoundnry - C++ Program to Implement Sieve of Atkins
Stackoverflow - Comparison of Sieve of Sundaram and Sieve of Atkin for generating a list of prime numbers
'개발 > Algorithm' 카테고리의 다른 글
| 행렬 곱셈 연산 최적화 (0) | 2019.10.22 |
|---|---|
| 순열 알고리즘 (Permutation Algorithm) (3) | 2019.09.06 |
| [C++ STL] 벡터 컨테이너(Vector) (0) | 2019.07.28 |
- Total
- Today
- Yesterday
- UE4
- GoogleTest
- C7568
- Perforce Stream
- P4 Stream
- 구글테스트
- C# 람다식
- C++ Compile error
- 행렬
- C# lambda expression
- Perforce Streams
- code copyright
- visual studio 핫 리로드
- c++ 핫 리로드
- C# 익명함수
- DXGI
- c++ hot reload
- P4 Streams
- 언리얼 엔진
- 퍼포스 개요
- 알고리즘
- Visual Studio C1083
- 퍼포스 스트림
- 구간합
- 코드 저작권
- visual studio hot reload
- Auto
- game hot reload
- MSVC C1083
- C++
| 일 | 월 | 화 | 수 | 목 | 금 | 토 |
|---|---|---|---|---|---|---|
| 1 | 2 | |||||
| 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| 10 | 11 | 12 | 13 | 14 | 15 | 16 |
| 17 | 18 | 19 | 20 | 21 | 22 | 23 |
| 24 | 25 | 26 | 27 | 28 | 29 | 30 |