আমাদের একটি ধনাত্মক সংখ্যা n ইনপুট হিসেবে দেওয়া হয়েছে। লক্ষ্য হল এমন জোড়া (i, j) এর সংখ্যা বের করা যাতে i + j একটি মুক্তিক সংখ্যা হয় এবং সেটি n-এর চেয়ে ছোট। এছাড়া i != j এবং i, j >= 1।
যদি n = 4 হয়, তবে শুধু একটি জোড়া সম্ভব: (1, 2) কারণ 1+2=3 যা মুক্তিক এবং ৪-এর চেয়ে ছোট।
উদাহরণ
ইনপুট: n = 7
আউটপুট: ৩
ব্যাখ্যা: জোড়াগুলো: (1,2), (1,4), (2,3)। যোগফল: ৩, ৫, ৫ — সব মুক্তিক এবং ৭-এর চেয়ে ছোট।
ইনপুট: n = 10
আউটপুট: ৬
ব্যাখ্যা: জোড়াগুলো: (1,2), (1,4), (2,3), (1,6), (2,5), (3,4)। যোগফল: ৩, ৫, ৫, ৭, ৭, ৭।
অ্যালগরিদম (Sieve of Sundaram)
- ভেরিয়েবল
nইনপুট নিন। prime_pair(int n)ফাংশনটি জোড়া সংখ্যা ফেরত দেবে।- প্রাথমিক কাউন্ট ০।
- Sieve of Sundaram ইনপুট
n-এর জন্য2*n+2পর্যন্ত মুক্তিক সংখ্যা দেয়। তাইn-কে অর্ধেক করেtemp_2 = (n-2)/2সংরক্ষণ করুন। Check[]অ্যারে তৈরি করুন দৈর্ঘ্যtemp_2এবং সব এলিমেন্টfalseদিয়ে ইনিশিয়ালাইজ করুন।check_prime(bool check[], int temp)ফাংশনেi+j+2*i*jরূপের সংখ্যাগুলোtrueচিহ্নিত করুন।Check[]ট্রাভার্স করুন: যেসব ইনডেক্সেfalseআছে, সেসবके জন্য মুক্তিক সংখ্যাtemp = 2*i + 1।- যে মুক্তিক সংখ্যা পাওয়া যাবে, তার জন্য ভিন্ন জোড়া সংখ্যা হবে
temp/2। এটি কাউন্টে যোগ করুন। - লুপ শেষে মোট জোড়া সংখ্যা ফেরত দিন।
C++ বাস্তবায়ন
#include <bits/stdc++.h>
using namespace std;
void check_prime(bool check[], int temp) {
for (int i = 1; i <= temp; i++) {
for (int j = i; (i + j + 2*i*j) <= temp; j++) {
check[i + j + 2*i*j] = true;
}
}
}
int prime_pair(int n) {
int count = 0;
int temp;
int temp_2 = (n - 2) / 2;
bool check[temp_2 + 1];
memset(check, false, sizeof(check));
check_prime(check, temp_2);
for (int i = 1; i <= temp_2; i++) {
if (check[i] == false) {
temp = 2*i + 1;
count += (temp / 2);
}
}
return count;
}
int main() {
int n = 10;
cout << "Count of pairs with sum as a prime number and less than n are: " << prime_pair(n);
return 0;
}
আউটপুট
Count of pairs with sum as a prime number and less than n are: 6
