এই সমস্যায়, আমাদের Q প্রশ্ন দেওয়া হয়েছে প্রতিটিতে একটি করে N নম্বর রয়েছে। আমাদের কাজ হল C++ এ 1 থেকে N পর্যন্ত ক্রমহীন কপ্রাইম জোড়ার সংখ্যা গণনা করার জন্য প্রশ্নগুলি সমাধান করার জন্য একটি প্রোগ্রাম তৈরি করা।
কো-প্রাইম তুলনামূলকভাবে প্রাইম বা পারস্পরিক প্রাইম নামেও পরিচিত হল সংখ্যার জোড়া যার শুধুমাত্র একটি ফ্যাক্টর অর্থাৎ 1।
সমস্যাটি বোঝার জন্য একটি উদাহরণ নেওয়া যাক,
ইনপুট :Q =2, প্রশ্ন =[5, 6]
আউটপুট :10
ব্যাখ্যা
জোড়াগুলো হল:(1, 1), (1, 2), (1, 3), (1, 4), (1, 5), (2, 3), (2, 5), (3, 4) ), (3, 5), (4, 5)
সমাধান পদ্ধতি
সমস্যার সবচেয়ে প্রতিশ্রুতিশীল সমাধান হল অয়লারের টোটিয়েন্ট ফাংশন phi(N) ব্যবহার করা। phi(N) প্রদত্ত মান N পর্যন্ত সহ-প্রাথমের মোট সংখ্যা গণনা করে। অয়লারের টোটিয়েন্ট ফাংশন হল,
$$𝛷(𝑁) =𝑁 ∏𝑁/𝑁 (1 −),$$
যেখানে p হল N.
এর সমস্ত মৌলিক গুণনীয়কএখন, আমরা N পর্যন্ত অ-অর্ডারড কপ্রাইম জোড়ার সংখ্যার গণনার মান প্রাক-গণনা করব। এবং তারপর পূর্বনির্ধারিত অ্যারে থেকে প্রতিটি প্রশ্নের মান খুঁজে বের করব।
উদাহরণ
#include <iostream>
using namespace std;
#define N 10001
int phi[N];
int CoPrimePairs[N];
void computePhi(){
for (int i = 1; i < N; i++)
phi[i] = i;
for (int p = 2; p < N; p++) {
if (phi[p] == p) {
phi[p] = p - 1;
for (int i = 2 * p; i < N; i += p) {
phi[i] = (phi[i] / p) * (p - 1);
}
}
}
}
void findCoPrimes() {
computePhi();
for (int i = 1; i < N; i++)
CoPrimePairs[i] = CoPrimePairs[i - 1] + phi[i];
}
int main() {
findCoPrimes();
int Q = 3;
int query[] = { 5, 7, 9};
for (int i = 0; i < Q; i++)
cout<<"For Query "<<(i+1)<<": Number of prime pairs is "<<CoPrimePairs[query[i]]<<endl;
return 0;
} আউটপুট
For Query 1: Number of prime pairs is 10 For Query 2: Number of prime pairs is 18 For Query 3: Number of prime pairs is 28
