소수는 1보다 큰 자연수 중 1과 자기 자신만을 약수로 가지는 수를 의미합니다. 예를 들어, 2, 3, 5, 7 등은 소수입니다. 특정 자연수 N이 소수인지 판별하거나, 주어진 범위 내의 모든 소수를 찾아내는 것은 컴퓨터 과학에서 자주 다루는 기본적인 문제입니다. 이 글에서는 다양한 소수 판별 및 소수 생성 알고리즘과 그 최적화 과정을 살펴보겠습니다.
단일 소수 판별
1. 기본 판별법 (O(N) 시간 복잡도)
가장 직관적인 방법은 2부터 N-1까지의 모든 정수로 N을 나누어보는 것입니다. 만약 N이 이 범위의 어떤 수로도 나누어떨어지지 않으면 N은 소수입니다. 중간에 나누어떨어지는 수를 발견하면 N은 소수가 아니므로 즉시 판별을 종료할 수 있습니다.
#include <iostream> // C++ 표준 입출력
#include <cstdio> // scanf 사용을 위해
#include <vector> // (사용하지는 않지만 일반적으로 포함)
int main() {
int input_num;
scanf("%d", &input_num);
bool is_prime = true; // 소수 여부를 나타내는 플래그
if (input_num <= 1) { // 1 이하는 소수가 아님
is_prime = false;
} else {
for (int i = 2; i < input_num; ++i) {
if (input_num % i == 0) {
is_prime = false; // 약수를 찾았으므로 소수가 아님
break;
}
}
}
if (is_prime) {
printf("yes\n");
} else {
printf("no\n");
}
return 0;
}
2. N/2까지 확인 (O(N/2) 시간 복잡도)
N이 약수를 가진다면, 그 약수는 반드시 N/2보다 작거나 같을 수밖에 없습니다 (자기 자신을 제외). 따라서 반복 범위를 2부터 N/2까지로 줄일 수 있습니다.
// ... (이전 코드의 나머지 부분)
if (input_num <= 1) {
is_prime = false;
} else {
for (int i = 2; i <= input_num / 2; ++i) { // N/2까지 확인
if (input_num % i == 0) {
is_prime = false;
break;
}
}
}
// ... (이전 코드의 나머지 부분)
3. 제곱근까지 확인 (O(√N) 시간 복잡도)
만약 N이 합성수라면, N은 항상 √N보다 작거나 같은 약수를 적어도 하나 가집니다. 이는 N의 약수 `a`가 있다면 `N = a * b` 형태가 되고, `a`와 `b` 중 하나는 반드시 √N보다 작거나 같기 때문입니다. 따라서 반복 범위를 2부터 √N까지로 대폭 줄일 수 있습니다.
#include <iostream>
#include <cstdio>
#include <cmath> // sqrt 함수 사용을 위해
int main() {
int input_num;
scanf("%d", &input_num);
bool is_prime = true;
if (input_num <= 1) {
is_prime = false;
} else {
// 루프 범위를 sqrt(input_num)까지로 제한
for (int i = 2; i * i <= input_num; ++i) { // i <= sqrt(input_num)과 동일
if (input_num % i == 0) {
is_prime = false;
break;
}
}
}
if (is_prime) {
printf("yes\n");
} else {
printf("no\n");
}
return 0;
}
4. 짝수 제외 및 6k ± 1 최적화 (O(√N/3) 시간 복잡도)
2와 3을 제외한 모든 소수는 6k-1 또는 6k+1 형태를 가집니다. 이는 6으로 나눈 나머지가 0, 2, 3, 4인 경우는 각각 2 또는 3의 배수이기 때문입니다 (6k는 2와 3의 배수, 6k+2는 2의 배수, 6k+3은 3의 배수, 6k+4는 2의 배수). 따라서 2와 3을 특별 처리한 후, 5부터 시작하여 6씩 증가하며 i와 i+2 (즉, 6k-1과 6k+1 형태)만 확인하면 됩니다.
#include <iostream>
#include <cstdio>
#include <cmath>
int main() {
int input_num;
scanf("%d", &input_num);
bool is_prime = true;
if (input_num <= 1) {
is_prime = false;
} else if (input_num == 2 || input_num == 3) { // 2와 3은 소수
is_prime = true;
} else if (input_num % 2 == 0 || input_num % 3 == 0) { // 2 또는 3의 배수는 소수가 아님
is_prime = false;
} else {
// 5부터 시작하여 6k-1, 6k+1 형태만 확인
for (int i = 5; i * i <= input_num; i = i + 6) {
if (input_num % i == 0 || input_num % (i + 2) == 0) {
is_prime = false;
break;
}
}
}
if (is_prime) {
printf("yes\n");
} else {
printf("no\n");
}
return 0;
}
범위 내 소수 생성 (소수 체)
단일 숫자에 대한 소수 판별은 효율적이지만, 특정 범위(예: 1부터 N까지)의 모든 소수를 찾아야 할 때는 비효율적입니다. 이 경우 '소수 체(Sieve)' 알고리즘을 사용합니다.
1. 단순 반복 및 판별 (O(N√N) 시간 복잡도)
1부터 N까지의 모든 숫자에 대해 위에서 설명한 최적화된 소수 판별 함수를 적용하는 방법입니다. 간단하지만, N이 커질수록 성능 저하가 뚜렷합니다.
#include <iostream>
#include <cstdio>
#include <cmath>
// 주어진 숫자가 소수인지 판별하는 함수
bool is_prime_optimized(int num) {
if (num <= 1) return false;
if (num == 2 || num == 3) return true;
if (num % 2 == 0 || num % 3 == 0) return false;
for (int i = 5; i * i <= num; i = i + 6) {
if (num % i == 0 || num % (i + 2) == 0) {
return false;
}
}
return true;
}
int main() {
int limit_N;
scanf("%d", &limit_N);
int prime_count = 0;
for (int i = 2; i <= limit_N; ++i) {
if (is_prime_optimized(i)) {
prime_count++;
}
}
printf("%d\n", prime_count);
return 0;
}
2. 에라토스테네스의 체 (O(N log log N) 시간 복잡도)
에라토스테네스의 체는 특정 범위 내의 모든 소수를 찾는 가장 고전적이고 효율적인 방법 중 하나입니다. 이 방법은 소수의 배수들을 지워나가면서 소수를 걸러냅니다.
- 1부터 N까지의 모든 숫자가 소수라고 가정하고 배열을 초기화합니다.
- 2부터 시작하여 현재 숫자가 소수라면, 그 숫자의 모든 배수를 소수가 아니라고 표시합니다.
- 다음으로 소수라고 표시된 숫자를 찾아 2단계 과정을 반복합니다. 이 과정은 N의 제곱근까지 진행하면 충분합니다.
#include <iostream>
#include <cstdio>
#include <vector> // bool형 배열 대신 vector<bool> 사용
int main() {
int limit_N;
scanf("%d", &limit_N);
// is_prime[i]가 true이면 i는 소수, false이면 합성수
std::vector<bool> is_prime(limit_N + 1, true);
is_prime[0] = false; // 0은 소수 아님
is_prime[1] = false; // 1은 소수 아님
// 2부터 N의 제곱근까지 반복
for (int p = 2; p * p <= limit_N; ++p) {
// p가 소수라면 p의 배수들을 제거
if (is_prime[p]) {
// p*p부터 시작하는 이유는 p*(2~p-1)는 이미 더 작은 소수에 의해 처리되었기 때문
for (int multiple = p * p; multiple <= limit_N; multiple += p) {
is_prime[multiple] = false;
}
}
}
int prime_count = 0;
for (int i = 2; i <= limit_N; ++i) {
if (is_prime[i]) {
prime_count++;
}
}
printf("%d\n", prime_count);
return 0;
}
3. 오일러의 체 (선형 체, O(N) 시간 복잡도)
에라토스테네스의 체는 같은 합성수가 여러 소수에 의해 중복해서 표시될 수 있다는 단점이 있습니다(예: 12는 2, 3에 의해 각각 지워짐). 오일러의 체는 이를 개선하여 모든 합성수가 '가장 작은 소인수'에 의해 단 한 번만 지워지도록 하여 선형 시간 복잡도 O(N)을 달성합니다.
- 1부터 N까지 모든 숫자를 소수라고 가정하고 배열을 초기화합니다.
- 소수 목록을 저장할 빈 배열을 준비합니다.
- 2부터 N까지 반복하며 숫자를 처리합니다.
- 현재 숫자가 소수라면(아직 지워지지 않았다면), 소수 목록에 추가합니다.
- 현재 숫자
i와 소수 목록의 각 소수p에 대해 다음 작업을 수행합니다:i * p가 N을 초과하면 반복을 중단합니다.i * p를 소수가 아니라고 표시합니다.- 만약
i가p의 배수라면, 현재i에 대해 더 큰 소수와의 곱을 처리하는 것을 중단합니다. 이는i * (p 다음 소수)가p * (i 다음 소수)형태에서 이미 지워질 것이기 때문에 중복 작업을 피하기 위함입니다.
#include <iostream>
#include <cstdio>
#include <vector>
int main() {
int limit_N;
scanf("%d", &limit_N);
std::vector<bool> is_prime(limit_N + 1, true); // 소수 여부
std::vector<int> primes_list; // 찾은 소수들을 저장할 리스트
int prime_count = 0;
is_prime[0] = false;
is_prime[1] = false;
for (int i = 2; i <= limit_N; ++i) {
if (is_prime[i]) { // i가 소수이면
primes_list.push_back(i); // 소수 목록에 추가
prime_count++;
}
// 현재 숫자 i와 찾은 소수들의 곱을 지워나감
for (int p : primes_list) {
// i * p 가 limit_N을 초과하면 더 이상 지울 필요 없음
if ((long long)i * p > limit_N) {
break;
}
is_prime[i * p] = false; // i * p는 합성수
// 핵심: i가 p의 배수이면, i*p는 p를 가장 작은 소인수로 가짐.
// 이후의 더 큰 소수 (p')에 대해 i*p'를 지우는 것은,
// (i/p)*p*p' 가 되므로 (i/p)*p'가 이미 p에 의해 지워졌을 것임.
// 따라서 중복 제거를 위해 여기서 break
if (i % p == 0) {
break;
}
}
}
printf("%d\n", prime_count);
return 0;
}
알고리즘을 최적화할수록 시간 복잡도는 낮아지지만, 더 많은 메모리(배열)를 필요로 합니다. 어떤 알고리즘을 사용할지는 해결해야 할 문제의 제약 조건(예: N의 크기, 시간/메모리 제한)에 따라 선택해야 합니다.