C++ में N तक की संख्याओं की गिनती जिनका अभाज्य संख्याओं की गिनती से अंतर K से अधिक या बराबर है

समस्या विवरण

दो पूर्णांक N और K दिए गए हैं, लक्ष्य उन संख्याओं की संख्या ज्ञात करना है जो निम्न शर्तों का पालन करती हैं:

संख्या <= N
| संख्या - count | >= K जहां count उस संख्या से कम या बराबर अभाज्य संख्याओं की संख्या है।

उदाहरण

इनपुट

N = 5, K = 2

आउटपुट

संख्याओं की गिनती: 2

व्याख्या

शर्तों का पालन करने वाली संख्याएं: 5 (5-2>=2) और 4 (4-2>=2)

इनपुट

N = 10, K = 6

आउटपुट

संख्याओं की गिनती: 1

व्याख्या

शर्तों का पालन करने वाली संख्याएं: 10 (10-4>=6)

दृष्टिकोण

इस दृष्टिकोण में हम बाइनरी सर्च का उपयोग करके अपनी गणनाओं को कम करेंगे। यदि num तक की अभाज्य संख्याओं की गिनती count1 है और संख्या num+1 के लिए यह गिनती count2 है। तब अंतर num+1 - count2 >= num - count1। इसलिए यदि num वैध है, तो num+1 भी वैध होगा। बाइनरी सर्च का उपयोग करके पाई गई पहली संख्या, मान लें num, जो शर्त का पालन करती है, तो num+1 भी उसी शर्त का पालन करेगी। इस तरह num से N तक की सभी संख्याओं की गिनती की जाएगी।

एल्गोरिदम चरण

चर N और K इनपुट के रूप में लें।
सरणी arr[] का उपयोग इंडेक्स i पर i तक की अभाज्य संख्याओं की गिनती संग्रहीत करने के लिए किया जाता है।
फंक्शन set_prime() अभाज्य संख्याओं की गिनती संग्रहीत करने के लिए सरणी arr[] को अपडेट करता है।
सरणी check[i] true संग्रहीत करती है यदि i अभाज्य है अन्यथा false।
check[0] = check[1] = false सेट करें क्योंकि वे गैर-अभाज्य हैं।
इंडेक्स i=2 से i*i < size(1000001) तक check को पार करें। और यदि कोई check[i] 1 है, तो संख्या अभाज्य है, फिर j=i*2 से j < size तक सभी check[j] को 0 से सेट करें।
अब for लूप का उपयोग करके arr[] को पार करें और इसे अपडेट करें। arr[i] = arr[i-1] तक की सभी गिनती। यदि arr[i] स्वयं अभाज्य है तो वह गिनती 1 से बढ़ जाएगी। arr[i]++ सेट करें।
फंक्शन total(int N, int K) N और K लेता है और संख्याओं की गिनती लौटाता है।
set_prime() कॉल करें।
temp_1 = 1 और temp_2 = N लें। प्रारंभिक गिनती 0 लें।
अब बाइनरी सर्च का उपयोग करके, while लूप में set = (temp_1 + temp_2) >> 1 ((first+last)/2) लें।
यदि set - arr[set] >= K तो शर्त पूरी होती है, count को set से अपडेट करें और temp_2 = set - 1।
अन्यथा temp_1 = set + 1 सेट करें।
अंत में count को न्यूनतम वैध संख्या N - count + 1 या 0 के रूप में सेट करें।
सभी लूप के अंत में परिणाम के रूप में गिनती लौटाएं।

C++ कोड उदाहरण

#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 << "संख्याओं की गिनती: " << total(N, K);
    return 0;
}

आउटपुट

संख्याओं की गिनती: 4