এই সমস্যায়, আমাদের একটি পূর্ণসংখ্যা N দেওয়া হয়েছে এবং আমাদের সমস্ত প্রথপ্রাইম সংখ্যা প্রিন্ট করতে হবে N এর থেকে কম বা সমান।
প্রথ প্রাইম নম্বর
একটি প্রোথ মৌলিক সংখ্যা একটি ধনাত্মক পূর্ণসংখ্যা যার মান n =k * হিসাবে উপস্থাপন করা যেতে পারে 2 n + 1. যেখানে k একটি বিজোড় ধনাত্মক পূর্ণসংখ্যা এবং n একটি ধনাত্মক পূর্ণসংখ্যা এবং উভয়ই 2 n কে সন্তুষ্ট করে> কে।
উদাহরণ − 3, 5, 13…..
বিষয়টি আরও ভালোভাবে বোঝার জন্য একটি উদাহরণ নেওয়া যাক -
Input: N = 23 Output: 3, 5, 13, 17.
এর জন্য, আমরা সমস্ত মৌলিক সংখ্যা N-এর চেয়ে কম খুঁজে পাব ) এবং প্রতিটি মৌলিক সংখ্যা প্রথ নম্বর কিনা তা পরীক্ষা করুন অথবা না. এবং সমস্ত প্রথ নম্বর প্রিন্ট করুন।
উদাহরণ
#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;
} আউটপুট
প্রোথ প্রাইম সংখ্যা 23 এর থেকে কম বা সমান −
3 5 13 17
