संख्याएं गिनें <=N जिसका अंतर उनके ऊपर अभाज्य संख्याओं की संख्या के साथ है> =K में C++

दो पूर्णांकों 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