Trong bài toán này, chúng ta được cho một số N. Nhiệm vụ là in ra tất cả các bộ ba số nguyên tố (prime triplet) nhỏ hơn N.
Prime triplet là tập hợp ba số nguyên tố. Chúng có dạng (p, p+2, p+6) hoặc (p, p+4, p+6). Tất cả các số nguyên tố được nhóm theo các bộ ba trên vì cứ mỗi ba số nguyên tố trong mẫu trực tiếp thì có một bội số của 6.
Hãy xem ví dụ sau để hiểu rõ vấn đề:
Input: N = 13 Output: 5 7 11
Để giải quyết, ta tìm tất cả các số nguyên tố nhỏ hơn hoặc bằng N. Sau đó kiểm tra các bộ ba.
Mã minh họa triển khai giải pháp:
Ví dụ
#include <bits/stdc++.h> using namespace std; void findPrimes(int n, bool prime[]) { for (int p = 2; p * p <= n; p++) { if (prime[p] == true) { for (int i = p * 2; i <= n; i += p) prime[i] = false; } } } void printPrimeTriplets(int n) { bool prime[n + 1]; memset(prime, true, sizeof(prime)); findPrimes(n, prime); for (int i = 2; i <= n-6; ++i) { if (prime[i] && prime[i + 2] && prime[i + 6]) cout<<i<<"\t"<<(i+2)<<"\t"<<(i+6)<<endl; else if (prime[i] && prime[i + 4] && prime[i + 6]) cout<<i <<"\t"<<(i + 4)<<"\t"<<(i + 6)<<endl; } } int main() { int N = 15; cout<<"Các bộ ba nguyên tố nhỏ hơn "<<N<<" là :\n"; printPrimeTriplets(N); return 0; }Kết quả
Các bộ ba nguyên tố nhỏ hơn 15 là : 5 7 11 7 11 13