휠 체(Wheel Sieve)는 주어진 범위 사이의 소수를 찾는 데 사용되는 방법입니다. 휠 인수분해(wheel factorization)는 에라토스테네스의 체(Sieve of Eratosthenes)를 본격적으로 수행하기 전에 소수와 합성수를 미리 걸러내는 과정을 시각적으로 수행하는 그래픽 기법입니다.
이 방법에서는 가장 안쪽 원에 배치된 소수들의 배수가 바깥쪽 원들에서도 자신과 같은 상대적 위치에 나타납니다. 그 결과 소수와 그 배수들이 마치 바퀴살(spoke)처럼 뻗어 나가는 형태를 이루게 되며, 안쪽 원의 소수들에 대한 배수들은 바깥쪽 원에서 합성수의 바퀴살을 형성합니다.
동작 원리
이 프로그램에서는 크기가 MAX_NUMBER인 정수 배열 prime을 사용합니다. 배열의 각 값은 다음과 같은 의미를 가집니다.
- 0: 아직 검사되지 않은 수
- 1: 소수로 확정된 수
- -1: 합성수(소수의 배수)로 표시된 수
2부터 시작하여 어떤 수 p가 아직 표시되지 않았다면 소수로 확정하고(1로 설정), p×2, p×3, … 처럼 p의 모든 배수를 -1로 표시하여 이후 검사에서 제외합니다. 이 과정을 범위 끝까지 반복하면 배열에는 소수만 1로 남게 됩니다.
알고리즘
시작
최대 숫자(MAX_NUMBER) 정의
gen_sieve_prime() 함수 호출
변수 c 선언 후 c = 2 대입
p = 2부터 최대 숫자까지 반복
만약 prime[p] == 0 이면
prime[p] = 1 로 설정
mul = p × c 계산
mul이 최대 숫자보다 작은 동안 반복
prime[mul] = -1 로 설정 (합성수 표시)
c 를 1 증가
mul = p × c 재계산
반복 종료
반복 종료
print_all_prime() 함수 호출
c = 0 대입
i = 0부터 최대 숫자까지 반복
만약 prime[i] == 1 이면
c 를 1 증가 (소수 개수 카운트)
c가 4보다 작으면
switch(c)
case 1 : 첫 번째 소수 출력
case 2 : 두 번째 소수 출력
case 3 : 세 번째 소수 출력
그 외에는
n번째 소수 형식으로 출력
끝
예제 코드
#include <iostream>
using namespace std;
#define MAX_NUMBER 40
int prime[MAX_NUMBER];
void gen_sieve_prime(void) {
for (int p = 2; p < MAX_NUMBER; p++) {
if (prime[p] == 0)
prime[p] = 1;
int c = 2;
int mul = p * c;
for (; mul < MAX_NUMBER;) {
prime[mul] = -1;
c++;
mul = p * c;
}
}
}
void print_all_prime() {
int c = 0;
for (int i = 0; i < MAX_NUMBER; i++) {
if (prime[i] == 1) {
c++;
if (c < 4) {
switch (c) {
case 1:
cout << c << "st prime is: " << i << endl;
break;
case 2:
cout << c << "nd prime is: " << i << endl;
break;
case 3:
cout << c << "rd prime is: " << i << endl;
break;
default:
break;
}
} else
cout << c << "th prime is: " << i << endl;
}
}
}
int main() {
gen_sieve_prime();
print_all_prime();
return 0;
}
실행 결과
MAX_NUMBER를 40으로 설정했을 때, 40 미만의 모든 소수가 순서대로 출력됩니다.
1st prime is: 2
2nd prime is: 3
3rd prime is: 5
4th prime is: 7
5th prime is: 11
6th prime is: 13
7th prime is: 17
8th prime is: 19
9th prime is: 23
10th prime is: 29
11th prime is: 31
12th prime is: 37
정리
휠 체는 에라토스테네스의 체를 시각적으로 이해하기 좋은 기법으로, 소수의 배수를 미리 제거함으로써 검사 대상을 줄여 줍니다. 위 예제는 O(N log log N)에 가까운 체 방식의 효율성을 그대로 활용하면서, 소수를 발견한 순서대로 서수(1st, 2nd, 3rd…)와 함께 출력하도록 구성되어 있습니다. MAX_NUMBER 값을 변경하면 원하는 범위까지 손쉽게 확장할 수 있습니다.