C++로 1부터 n까지의 소수 곱 구하기: 에라토스테네스의 체 활용법

문제 개요

숫자 n이 주어졌을 때, 1부터 n 사이에 존재하는 모든 소수의 곱을 구하는 프로그램을 작성해야 합니다. 예를 들어 n = 7이라면 소수는 2, 3, 5, 7이고, 2 × 3 × 5 × 7 = 210이므로 결과값은 210이 됩니다.

접근 방법: 에라토스테네스의 체

주어진 범위 내의 모든 소수를 효율적으로 찾기 위해 에라토스테네스의 체(Sieve of Eratosthenes) 알고리즘을 활용합니다. 이 방법은 다음과 같은 단계로 진행됩니다.

1. 크기가 n+1인 불리언 배열을 생성하고 모든 요소를 true로 초기화합니다.
2. 2부터 √n까지 반복하면서, 현재 수가 소수라면 그 수의 배수들을 모두 false(소수 아님)로 표시합니다.
3. 최종적으로 true로 남아 있는 값들이 바로 소수입니다.
4. 찾아낸 모든 소수를 차례로 곱하여 결과를 반환합니다.

에라토스테네스의 체의 시간 복잡도는 O(n log log n)으로, 각 숫자마다 소수 여부를 일일이 검사하는 방식보다 훨씬 효율적입니다.

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);
}

실행 결과

n = 8일 경우, 8 이하의 소수는 2, 3, 5, 7이므로 그 곱은 다음과 같이 출력됩니다.

Product of primes up to 8 is: 210

코드 설명

• PrimeProds(int n): 1부터 n까지의 소수 곱을 계산해 반환하는 함수입니다.
• 첫 번째 반복문으로 배열 전체를 true로 초기화하고, 두 번째 중첩 반복문에서 소수의 배수들을 제거합니다.
• i * i <= n 조건을 사용하면 √n까지만 검사해도 되므로 불필요한 연산을 줄일 수 있습니다.
• 마지막 반복문에서 prime[i]가 참인 모든 i를 곱해 최종 결과를 얻습니다.

참고로 소수의 곱은 n이 조금만 커져도 매우 빠르게 증가하므로, 실제 프로젝트에서는 오버플로우를 방지하기 위해 long long 자료형이나 임의 정밀도 연산을 고려하는 것이 좋습니다.