计数数字 <= N，在C ++中与素数计数的差为> = K

  • Z时代
  • 2024-01-10
  • 分类：综合

给定两个整数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也将是valid.For使用符合条件的二进制搜索找到的第一个数字，例如“ 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 <size(1000001)。并且如果任何check [i]为1，则数字为素数，然后将所有check [j]的值从j = i * 2设为0到j <size。

  • 现在使用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

以上是 计数数字 <= N，在C ++中与素数计数的差为> = K 的全部内容， 来源链接： utcz.com/z/315854.html

回到顶部