Trong hướng dẫn này, ta sẽ viết chương trình tìm hai số nguyên tố khác nhau có tích cho trước. Hãy xem một số ví dụ.
Đầu vào − 21
Đầu ra − 3 7
Ở đây, ta cần có tất cả số nguyên tố nhỏ hơn tích cho trước. Khi đã có các số nguyên tố đó, ta dễ dàng tìm cặp. Làm theo các bước sau.
- Khởi tạo tích và mảng boolean lưu trạng thái nguyên tố của các số trong phạm vi.
- Tìm tất cả số nguyên tố nhỏ hơn tích cho trước và lưu vào mảng.
- Duyệt đến tích cho trước.
- Nếu số hiện tại là nguyên tố và n / số_hiện_tại cũng là nguyên tố, kiểm tra xem chúng có khác nhau không.
- Nếu khác nhau, in ra.
Ví dụ
Xem mã dưới đây:
#include <bits/stdc++.h> using namespace std; bool primes(int n, bool primeStatus[]) { primeStatus[0] = primeStatus[1] = false; for (int i = 2; i <= n; i++) { primeStatus[i] = true; } for (int i = 2; i * i <= n; i++) { if (primeStatus[i] == true) { for (int j = i * 2; j <= n; j += i) primeStatus[j] = false; } } } int main() { int n = 21; bool primeStatus[n + 1], pairsFound = false; primes(n, primeStatus); for (int i = 2; i < n; i++) { int pair = n / i; if (primeStatus[i] && primeStatus[pair] && pair != i && pair * i == n) { cout << i << " " << pair << endl; pairsFound = true; break; } } if (!pairsFound){ cout << "No pairs"; } return 0; }
Đầu ra
Nếu chạy mã trên, bạn sẽ nhận được kết quả sau:
3 7
Kết luận
Nếu bạn có thắc mắc, hãy đề cập trong phần bình luận.