素数の数<=Nで、それまでの素数の数との差は、C++では>=Kです。

2つの整数NとKが与えられた場合、目標は、以下の条件に従うような数の数を見つけることです-

• 番号<=N

• |数カウント|> =Kここで、countは、Number以下の素数の数です。

例

入力

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の場合、この数はcount2です。次に、差num + 1-count2>=num-count1。したがって、numが有効な場合、num + 1も有効になります。最初に見つかった数値について、条件に従う二分探索を使用して「num」と言うと、「num」+1も同じ条件に従います。このようにして、numからNまでのすべての数値がカウントされます。

• 変数NとKを入力として受け取ります。

• 配列arr[]は、iまでの素数の数を格納するために使用されます。インデックスiに格納されます。

• 関数set_prime（）は、素数の数を格納するために配列arr[]を更新します。

• 配列check[i]は、iが素数の場合はtrueを格納し、それ以外の場合はfalseを格納します。

• check [0] =check [1] =falseに設定します。これは、素数ではないためです。

• インデックスi=2からi*i に設定します。

• 次に、forループを使用してarr []をトラバースし、更新します。 arr [i] =arr[i-1]までのすべてのカウント。 arr [i]自体が素数の場合、そのカウントは1ずつ増加します。arr[i]++を設定します。

• 関数total（int N、int K）は、Nと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の場合、条件が満たされ、setおよび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