दो पूर्णांकों 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 )
नीचे दिए गए कार्यक्रम में उपयोग किया गया दृष्टिकोण इस प्रकार है -
इस दृष्टिकोण में हम अपनी गणना को कम करने के लिए द्विआधारी खोज का उपयोग करेंगे। यदि संख्या तक अभाज्य संख्याओं की संख्या गिनती 1 है और संख्या संख्या + 1 के लिए यह गणना गिनती 2 है। फिर अंतर num+1−count2>=num−count1. इसलिए यदि num मान्य है, num+1 भी मान्य होगा। पहले नंबर के लिए, बाइनरी सर्च का उपयोग करके 'num' कहें, जो शर्त का पालन करता है, तो 'num'+1 भी उसी स्थिति का पालन करेगा। इस तरह num से N के बीच के सभी नंबर गिने जाएंगे।
-
इनपुट के रूप में चर N और K लें।
-
Array arr[] का उपयोग अभाज्य संख्याओं की संख्या को i तक संग्रहीत करने के लिए किया जाता है I सूचकांक i पर संग्रहीत किया जाएगा।
-
अभाज्य संख्याओं को संग्रहीत करने के लिए फ़ंक्शन set_prime() अद्यतन सरणी arr[]।
-
ऐरे चेक [i] सही स्टोर करता है अगर मैं प्राइम हूं और झूठा स्टोर करता है।
-
चेक सेट करें [0] =चेक [1] =झूठा क्योंकि वे गैर अभाज्य हैं।
-
इंडेक्स i=2 से i*i
-
अब लूप के लिए ट्रैवर्स एआर [] का उपयोग करें और इसे अपडेट करें। arr[i]=arr[i−1] तक सभी मायने रखता है। यदि arr[i] स्वयं अभाज्य है तो वह संख्या 1 से बढ़ जाएगी। arr[i]++ सेट करें।
-
फंक्शन टोटल (इंट एन, इंट के) एन और के लेता है और संख्याओं की संख्या देता है <=एन जिसका अंतर उनके ऊपर की संख्या के साथ है> =के।
-
कॉल सेट_प्राइम ()।
-
temp_1=1 और temp_2=N लें। प्रारंभिक गणना 0 के रूप में लें।
-
अब बाइनरी सर्च का उपयोग करते हुए, लूप में सेट करें =(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
