資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究使用 C++ 統計小於等於 N 的數字，其與小於等於該數字的素數個數之差大於等於 K
給定兩個整數 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 )
**下面程式中使用的演算法如下：**
在這種方法中，我們將使用二分查詢來減少計算量。如果小於等於 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 迴圈中設定 = (temp_1 + temp_2) >> 1 ((first+last) /2)。
如果 set - arr[set] >= K，則滿足條件，將計數更新為 set 並將 temp_2 = set - 1。
否則，將 temp_1 = temp_1 + 1。
最後將計數設定為最小有效數字 N - 計數 + 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
111 次檢視
