এই সমস্যায়, একটি পূর্ণসংখ্যা N দেওয়া থাকে এবং N-এর চেয়ে ছোট বা সমান সব প্রথ প্রাইম নম্বর প্রিন্ট করতে হবে।
প্রথ প্রাইম নম্বর
একটি প্রথ প্রাইম নম্বর হলো একটি ধনাত্মক পূর্ণসংখ্যা যার মান নিচের ফর্মুলা দিয়ে প্রকাশ করা যায়: n = k × 2ⁿ + 1। যেখানে k একটি বিজোড় ধনাত্মক পূর্ণসংখ্যা এবং n একটি ধনাত্মক পূর্ণসংখ্যা, এবং দুটোই 2ⁿ > k শর্তটি পূরণ করে।
উদাহরণ: 3, 5, 13...
উদাহরণ দিয়ে বুঝি:
ইনপুট: N = 23 আউটপুট: 3, 5, 13, 17
এই জন্য, আমরা N-এর চেয়ে ছোট সব প্রাইম নম্বর খুঁজে বের করব (এраво এρατοস্থেনিসের ছাঁনি বা Sieve of Eratosthenes ব্যবহার করে)। এবং প্রতিটি প্রাইম নম্বর প্রথ নম্বর কিনা তা চেক করব। এবং সব প্রথ নম্বর প্রিন্ট করব।
C++ উদাহরণ
#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; }আউটপুট
২৩-এর চেয়ে ছোট বা সমান প্রথ প্রাইম নম্বরগুলো হলো:
3 5 13 17
