N এবং K দুটি পূর্ণসংখ্যা দেওয়া হয়েছে, লক্ষ্য হল সংখ্যার গণনা খুঁজে বের করা যাতে তারা নীচের শর্তগুলি অনুসরণ করে -
-
নম্বর<=N
-
| সংখ্যা−গণনা |>=K যেখানে গণনা হল সংখ্যার চেয়ে কম বা সমান মৌলিক সংখ্যার সংখ্যা।
উদাহরণস্বরূপ
ইনপুট
N = 5, K = 2
আউটপুট
Count of numbers < = N whose difference with the count of primes upto them is > = K are: 2
ব্যাখ্যা
The numbers that follow the conditions are: 5 ( 5−2>=2 ) and 4 ( 4−2>=2 )
ইনপুট
N = 10, K = 6
আউটপুট
Count of numbers < = N whose difference with the count of primes upto them is > = K are: 1
ব্যাখ্যা
The numbers that follow the conditions are: 10 ( 10−4>=6 )
নিম্নলিখিত প্রোগ্রামে ব্যবহৃত পদ্ধতি −
এই পদ্ধতিতে আমরা আমাদের গণনা কমাতে বাইনারি অনুসন্ধান ব্যবহার করব। যদি num পর্যন্ত মৌলিক সংখ্যার গণনা হয় count1 এবং সংখ্যা num+1-এর জন্য এই গণনাটি গণনা2 হয়। তারপর পার্থক্য num+1−count2>=num−count1. তাই যদি num বৈধ হয়, num+1ও বৈধ হবে। প্রথম নম্বর পাওয়া যাওয়ার জন্য, বাইনারি সার্চ ব্যবহার করে 'num' বলুন যা শর্ত অনুসরণ করে, তারপর 'num'+1ও একই শর্ত অনুসরণ করবে। এইভাবে num থেকে N পর্যন্ত সমস্ত সংখ্যা গণনা করা হবে।
-
ইনপুট হিসাবে N এবং K ভেরিয়েবল নিন।
-
অ্যারে arr[] ব্যবহার করা হয় i পর্যন্ত মৌলিক সংখ্যার গণনা সূচী i এ সংরক্ষণ করা হবে।
-
ফাংশন সেট_প্রাইম() প্রাইম গণনা সংরক্ষণের জন্য অ্যারে অ্যারে[] আপডেট করে।
-
অ্যারে চেক[i] সঞ্চয় করে সত্য যদি i প্রাইম হয় অন্যথায় মিথ্যা সঞ্চয় করে।
-
সেট চেক[0]=চেক[1] =মিথ্যা কারণ তারা নন প্রাইম।
-
সূচী i=2 থেকে i*i
-
এখন ট্রাভার্স arr[] লুপ ব্যবহার করে আপডেট করুন। arr[i]=arr[i−1] পর্যন্ত সমস্ত গণনা। যদি arr[i] নিজেই প্রাইম হয় তাহলে সেই সংখ্যা 1 দ্বারা বৃদ্ধি পাবে। arr[i]++ সেট করুন।
-
ফাংশনের মোট (int N, int K) N এবং K নেয় এবং সংখ্যার সংখ্যা প্রদান করে <=N যার প্রাইম গণনার সাথে তাদের পর্যন্ত পার্থক্য হল> =K।
-
সেট_প্রাইম() কে কল করুন।
-
temp_1=1 এবং temp_2=N নিন। 0 হিসাবে প্রাথমিক গণনা নিন।
-
এখন বাইনারি অনুসন্ধান ব্যবহার করে, while লুপ টেক সেট =(temp_1 + temp_2)>> 1 ((প্রথম+শেষ) /2)।
-
যদি set−arr[set] হয়>=K তাহলে শর্ত পূরণ হয়, সেট এবং temp_2=set−1 সহ গণনা আপডেট করুন।
-
অন্যথায় temp_1=temp_1+1 সেট করুন।
-
শেষে ন্যূনতম বৈধ সংখ্যা হিসাবে গণনা সেট করুন N−count+1 বা 0।
-
সমস্ত লুপের শেষে ফলাফল হিসাবে গণনা ফিরে আসে।
উদাহরণ
#include <bits/stdc++.h>
using namespace std;
#define size 1000001
int arr[size];
void set_prime(){
bool check[size];
memset(check, 1, sizeof(check));
check[0] = 0;
check[1] = 0;
for (int i = 2; i * i < size; i++){
if(check[i] == 1){
for (int j = i * 2; j < size; j += i){
check[j] = 0;
}
}
}
for (int i = 1; i < size; i++){
arr[i] = arr[i − 1];
if(check[i] == 1){
arr[i]++;
}
}
}
int total(int N, int K){
set_prime();
int temp_1 = 1;
int temp_2 = N;
int count = 0;
while (temp_1 <= temp_2){
int set = (temp_1 + temp_2) >> 1;
if (set − arr[set] >= K){
count = set;
temp_2 = set − 1;
} else {
temp_1 = set + 1;
}
}
count = (count ? N − count + 1 : 0);
return count;
}
int main(){
int N = 12, K = 5;
cout<<"Count of numbers < = N whose difference with the count of primes upto them is > = K are: "<<total(N, K);
return 0;
} আউটপুট
যদি আমরা উপরের কোডটি চালাই তবে এটি নিম্নলিখিত আউটপুট −
উৎপন্ন করবেCount of numbers < = N whose difference with the count of primes upto them is > = K are: 4
