Trong bài toán này, chúng ta được cho một số n. Nhiệm vụ là in ra số primorial của nó.
Số primorial (Pn#) là số bằng tích của n số nguyên tố đầu tiên.
Số primorial tương tự như giai thừa của n. Khác biệt là giai thừa dùng mọi số, còn primorial chỉ dùng các số nguyên tố.
Hãy xem ví dụ sau để hiểu rõ vấn đề:
Input: N = 4 Output 210 Giải thích: Số primorial, Pn# = 2 * 3 * 5 * 7 = 210
Để giải quyết, ta tìm n số nguyên tố đầu tiên. In tích của tất cả các số nguyên tố đến n, đó là giá trị của số primorial.
Ví dụ
Chương trình minh họa triển khai giải pháp:
#include<bits/stdc++.h> using namespace std; const int MAX = 1000000; vector <int> primeNumbers; void findPrimes() { bool marked[MAX/2 + 1] = {0}; for (int i = 1; i <= (sqrt(MAX)-1)/2 ; i++) for (int j = (i*(i+1))<<1 ; j <= MAX/2 ; j += 2*i +1) marked[j] = true; primeNumbers.push_back(2); for (int i=1; i<=MAX/2; i++) if (marked[i] == false) primeNumbers.push_back(2*i + 1); } int findPrimorial(int n) { findPrimes(); int result = 1; for (int i=0; i<n; i++) result = result * primeNumbers[i]; return result; } int main() { int N = 6; cout<<"Primorial(P#) của "<<N<<" số nguyên tố đầu tiên là "<<findPrimorial(N)<<endl; return 0; }Kết quả
Primorial(P#) của 6 số nguyên tố đầu tiên là 30030