ในปัญหานี้ เราได้รับจำนวนเต็ม N และเราต้องพิมพ์ หมายเลข prothprime ทั้งหมด น้อยกว่าหรือเท่ากับ N.
โปรทไพรม์นัมเบอร์
จำนวนเฉพาะของ proth เป็นจำนวนเต็มบวกที่มีค่าเป็น n =k * 2 น + 1. โดยที่ k เป็นจำนวนเต็มบวกคี่ และ n เป็นจำนวนเต็มบวก และทั้งคู่เป็นไปตาม 2 n > ก.
ตัวอย่าง − 3, 5, 13…..
มาดูตัวอย่างเพื่อทำความเข้าใจหัวข้อกันดีกว่า −
Input: N = 23 Output: 3, 5, 13, 17.
สำหรับสิ่งนี้ เราจะหาจำนวนเฉพาะทั้งหมดที่น้อยกว่า N(สำหรับสิ่งนี้ เราจะใช้ ตะแกรงของ Eratosthenes ). และตรวจสอบว่าจำนวนเฉพาะแต่ละจำนวนเป็น จำนวนพหูพจน์ . หรือไม่ หรือไม่. และพิมพ์เลขโปรธทั้งหมด
ตัวอย่าง
#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<<"Proth Prime Numbers less than or equal to "<<n<<" are :\n";
SieveOfEratosthenes(n);
for (int i = 1; i <= n; i++)
if (isaProthPrime(i))
cout<<i<<"\t";
return 0;
} ผลลัพธ์
Proth Prime Numbers น้อยกว่าหรือเท่ากับ 23 คือ -
3 5 13 17
