C++-এ N-র চেয়ে ছোট বা সমান সংখ্যাগুলোর মধ্যে যাদের প্রাইম সংখ্যার কাউন্টের সাথে পার্থক্য K-র চেয়ে বড় বা সমান সেটির গণনা

দুটি ইন্টিজার N এবং K দেওয়া আছে। লক্ষ্য হলো সادات সংখ্যাগুলোর গণনা করা যারা নিচের শর্তগুলো পূরণ করে:

সংখ্যা ≤ N
| সংখ্যা - count | ≥ K যেখানে count হলো সেই সংখ্যা পর্যন্ত প্রাইম সংখ্যাগুলোর সংখ্যা।

উদাহরণ ১

ইনপুট

N = 5, K = 2

আউটপুট

N-র চেয়ে ছোট বা সমান সংখ্যাগুলোর মধ্যে যাদের প্রাইম সংখ্যার কাউন্টের সাথে পার্থক্য K-র চেয়ে বড় বা সমান সেটির গণনা: 2

ব্যাখ্যা

শর্ত পূরণকারী সংখ্যাগুলো: 5 (5-2>=2) এবং 4 (4-2>=2)

উদাহরণ ২

ইনপুট

N = 10, K = 6

আউটপুট

N-র চেয়ে ছোট বা সমান সংখ্যাগুলোর মধ্যে যাদের প্রাইম সংখ্যার কাউন্টের সাথে পার্থক্য K-র চেয়ে বড় বা সমান সেটির গণনা: 1

ব্যাখ্যা

শর্ত পূরণকারী সংখ্যাগুলো: 10 (10-4>=6)

প্রয়োগ করা পদ্ধতি

এই পদ্ধতিতে বাইনারি সার্চ ব্যবহার করে গণনা কমানো হয়। যদি num পর্যন্ত প্রাইম সংখ্যার কাউন্ট count1 এবং num+1 এর জন্য count2 হয়, তবে num+1-count2 >= num-count1। তাই যদি num বৈধ হয়, তবে num+1-ও বৈধ হবে। বাইনারি সার্চ দিয়ে প্রথম বৈধ সংখ্যা num বের করলে, num+1 থেকে N পর্যন্ত সব সংখ্যা বৈধ হবে।

ভেরিয়েবল N এবং K ইনপুট নিন।
arr[] অ্যারেতে i পর্যন্ত প্রাইম সংখ্যার কাউন্ট ইনডেক্স i-এ রাখা হয়।
set_prime() ফাংশনটি arr[] আপডেট করে প্রাইম সংখ্যাগুলোর কাউন্ট সংরক্ষণ করে।
check[i] অ্যারেতে i প্রাইম হলে true, নন-প্রাইম হলে false থাকে।
check[0]=check[1] = false সেট করুন কারণ এগুলো নন-প্রাইম।
check ট্রুভার্স করুন i=2 থেকে i*i < size(1000001) পর্যন্ত। যদি check[i] ১ হয় (প্রাইম), তবে j=i*2 থেকে j পর্যন্ত সকল check[j] ০ করুন।


এখন arr[] ট্রুভার্স করে আপডেট করুন। arr[i] = arr[i-1]। যদি i প্রাইম হয় তবে arr[i]++।
total(int N, int K) ফাংশনটি ফলাফল রিটার্ন করে।
set_prime() কল করুন।
temp_1=1 এবং temp_2=N নিন। আরম্ভিক কাউন্ট ০।
বাইনারি সার্চ দিয়ে while লুপে set = (temp_1 + temp_2) >> 1 ((first+last)/2) করুন।
যদি set - arr[set] >= K হয় তবে শর্ত পূরণ হয়, count = set এবং temp_2 = set - 1 আপডেট করুন।
অন্যথায় temp_1 = set + 1 সেট করুন।
শেষে কাউন্ট = ন্যূনতম বৈধ সংখ্যা N - count + 1 অথবা ০।
লুপ শেষে কাউন্ট রিটার্ন করুন ফলাফল হিসেবে।



উদাহরণ কোড
#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 << "N-র চেয়ে ছোট বা সমান সংখ্যাগুলোর মধ্যে যাদের প্রাইম সংখ্যার কাউন্টের সাথে পার্থক্য K-র চেয়ে বড় বা সমান সেটির গণনা: " << total(N, K); 
    return 0; 
}

আউটপুট
উপরোক্ত কোডটি রান করলে নিচের আউটপুটটি আসবে:
N-র চেয়ে ছোট বা সমান সংখ্যাগুলোর মধ্যে যাদের প্রাইম সংখ্যার কাউন্টের সাথে পার্থক্য K-র চেয়ে বড় বা সমান সেটির গণনা: 4