Cho số nguyên N, in ra tất cả các số nguyên tố Proth nhỏ hơn hoặc bằng N.
Số nguyên tố Proth
Số nguyên tố Proth là số nguyên dương có dạng n = k * 2^n + 1, với k là số nguyên lẻ dương, n là số nguyên dương, và thỏa mãn 2^n > k.
Ví dụ: 3, 5, 13...
Ví dụ bài toán:
Input: N = 23 Output: 3, 5, 13, 17
Giải pháp: Tìm tất cả số nguyên tố ≤ N (dùng sàng Eratosthenes). Kiểm tra từng số nguyên tố có phải số Proth hay không.
Chương trình minh họa
#include <bits/stdc++.h>
using namespace std;
int prime[1000];
void SieveOfEratosthenes(int n){
for (int i = 1; i <= n + 1; i++)
prime[i] = true;
prime[1] = false;
for (int p = 2; p * p <= n; p++) {
if (prime[p] == true) {
for (int i = p * p; i <= n; i += p)
prime[i] = false;
}
}
}
bool isTwosExponent(int n){
return (n && !(n & (n - 1)));
}
bool isaProthNumber(int n){
int k = 1;
while (k < (n / k)) {
if (n % k == 0) {
if (isTwosExponent(n / k))
return true;
}
k = k + 2;
}
return false;
}
bool isaProthPrime(int n){
if (isaProthNumber(n - 1)) {
if (prime[n])
return true;
else
return false;
}
else
return false;
}
int main(){
int n = 23;
cout << "Các số nguyên tố Proth ≤ " << n << " là :\n";
SieveOfEratosthenes(n);
for (int i = 1; i <= n; i++)
if (isaProthPrime(i))
cout << i << "\t";
return 0;
}
Kết quả
Các số nguyên tố Proth ≤ 23 là:
3 5 13 17