숫자 n이 주어졌을 때, 1부터 n 사이에 존재하는 모든 소수의 곱을 구하는 문제입니다. 예를 들어 n = 7이라면 소수는 2, 3, 5, 7이므로 곱은 2 × 3 × 5 × 7 = 210이 됩니다.
접근 방법
범위 내의 모든 소수를 효율적으로 찾기 위해 에라토스테네스의 체(Sieve of Eratosthenes) 알고리즘을 사용합니다. 이 알고리즘은 다음과 같은 순서로 동작합니다.
- 2부터 n까지의 모든 수를 일단 소수(true)로 표시합니다.
- 가장 작은 소수인 2부터 시작하여, 각 소수의 배수들을 모두 소수가 아닌 것(false)으로 표시합니다.
- 바깥 루프는 √n까지만 검사하면 됩니다. 그보다 큰 수의 합성수 여부는 이미 더 작은 소수들의 배수 제거 과정에서 걸러지기 때문입니다.
체가 완성되면 배열에 true로 남아 있는 값들이 곧 소수이며, 이들을 모두 곱하면 최종 결과를 얻을 수 있습니다.
C++ 코드 예제
#include<iostream>
using namespace std;
long PrimeProds(int n) {
bool prime[n + 1];
for(int i = 0; i<=n; i++){
prime[i] = true;
}
for (int i = 2; i * i <= n; i++) {
if (prime[i] == true) {
for (int j = i * 2; j <= n; j += i)
prime[j] = false;
}
}
long product = 1;
for (int i = 2; i <= n; i++)
if (prime[i])
product *= i;
return product;
}
int main() {
int n = 8;
cout << "Product of primes up to " << n << " is: " << PrimeProds(n);
}실행 결과
Product of primes up to 8 is: 210
n = 8일 때 8 이하의 소수는 2, 3, 5, 7이므로, 이들의 곱인 210이 출력됩니다.
코드 설명
PrimeProds(int n): 1부터 n까지의 소수 곱을 계산해 반환하는 함수입니다.bool prime[n + 1]: 각 인덱스의 수가 소수인지 여부를 저장하는 배열로, 초기에는 모두 true로 설정합니다.- 바깥 루프는 2부터 √n까지 검사하고, 안쪽 루프는 해당 소수의 배수(i×2부터 시작)를 false로 표시합니다.
- 마지막 루프에서 배열에 true로 남아 있는 값, 즉 소수들을 모두 곱해 결과를 반환합니다.
시간 복잡도와 주의 사항
에라토스테네스의 체의 시간 복잡도는 O(n log log n)으로, 각 수마다 일일이 소수 여부를 검사하는 O(n√n) 방식보다 훨씬 효율적입니다. 다만 소수의 곱은 값이 매우 빠르게 커지므로, n이 조금만 커져도 long 타입의 범위를 초과할 수 있습니다. 실제 응용에서는 unsigned long long 또는 임의 정밀도 정수(big integer) 라이브러리를 사용하는 것이 안전합니다.