একটি পরিসরের মধ্যে সমস্ত সম্ভাব্য সহ-প্রধান স্বতন্ত্র উপাদান জোড়া [L, R]?

এখানে আমরা দেখব কিভাবে পরিসর থেকে সহ-প্রাথমিক জোড়ার সংখ্যা গণনা করা যায়, যেখানে একটি সংখ্যা এক জোড়ার বেশি প্রদর্শিত হবে না।

যুক্তি নিয়ে আলোচনার আগে দেখা যাক কো-প্রাইম সংখ্যাগুলো কী কী? সহ-প্রাথমিক সংখ্যা হল সেই সংখ্যাগুলি যেগুলির শুধুমাত্র একটি ধনাত্মক পূর্ণসংখ্যা ভাজক, সেটি হল 1৷ অন্য কথায়, আমরা বলতে পারি এই দুটি সংখ্যার GCD হল 1৷

এখানে আমরা নিম্ন এবং উপরের সীমা প্রদান করছি। নিম্ন এবং উপরের সীমা 1 এবং 6 হলে, তিনটি জোড়া আছে। এগুলি হল (1, 2), (3, 4) এবং (5, 6)

এই সমস্যাটি সমাধানের পদ্ধতিটি এরকম:যদি সংখ্যাগুলি পরপর হয়, তবে তারা সর্বদা সহ-প্রধান। সুতরাং গণনা হবে (R – L + 1)/2। যদি (R – L + 1) বিজোড় হয় তবে একটি সংখ্যা অবশিষ্ট থাকবে, এটি কোনো জোড়ায় স্থান পাবে না, যদি এটি জোড় হয়, তাহলে সবাই জোড়া তৈরি করবে

অ্যালগরিদম

countCoPrimePairs(L, R)

Begin
   return (R – L + 1)/2
End

উদাহরণ

#include <iostream>
using namespace std;
int countCoPrimePairs(int L, int R) {
   return (R - L + 1)/2;
}
main() {
   int l = 1, r = 6;
   cout << "Number of co-prime pairs: " << countCoPrimePairs(l, r);
}

আউটপুট

Number of co-prime pairs: 3