資料結構
網路
關係型資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究C++ 中求和為素數且小於 n 的對數
給定一個正數 n 作為輸入。目標是找到可能的對數 (i,j)，使得每對的和 (i+j) 為素數且小於 n。 此外 i != j 且 i,j>=1 如果 n 為 4，則只有一種可能的對 (1,2)。 這裡 1+2 = 3 是素數且小於 4。 此外 1,2 >=1。
讓我們透過示例來理解。
輸入 − n=7
輸出 − 和為素數且小於 n 的對數為 - 3
說明 − 對將為 (1,2), (1,4), (2,3)。 和 3, 5, 5 為素數且小於 7。
輸入 − n=10
輸出 − 和為素數且小於 n 的對數為 - 6
說明−
對將為 (1,2), (1,4), (2,3), (1,6), (2,5), (3,4)。
和 3, 5, 5, 7, 7, 7 為素數且小於 10。
下面程式中使用的方案如下
在這種方案中，我們首先將使用 Sundaram 篩法在函式 check_prime(bool check[], int temp) 中找到所有小於 n 的素數。
此外，對於每個奇數 temp，具有和 temp 的不同對的數量將為 temp/2。
除了 2 之外，所有素數都是奇數，因此如果我們找到任何小於 n 的素數，我們將把 temp/2 加到對的數量中。
將變數 n 作為輸入。
函式 prime_pair(int n) 獲取 n 並返回和為素數且小於 n 的對的數量。
將初始計數設為 0。
由於 Sundaram 篩法為輸入 n 生成小於 2*n+2 的素數。 我們將 n 減少到一半並存儲在 temp_2 中。
建立一個長度為 temp_2 的陣列 Check[]，以將所有形式為 ( i+j+2*i*j ) 的數字標記為 True。 將其初始化為所有元素都為 false。
使用函式 check_prime(bool check[], int temp)，將 check[] 初始化為形式為 (i+j+2*i*j) 的數字的 true。 並且此和 < temp。
現在使用 for 迴圈從索引 i=0 到 i<temp_2 遍歷 Check[]。
對於每個 check[i] 為 false，素數將為 temp=2*i+1。
加起來等於 temp 的對將為 temp/2。
將 temp/2 加到計數中。
在 for 迴圈結束時，我們將擁有和為素數且小於 n 的總對數。
返回計數作為結果。
示例
#include <bits/stdc++.h>
using namespace std;
void check_prime(bool check[], int temp){
for (int i=1; i<=temp; i++){
for (int j=i; (i + j + 2*i*j) <= temp; j++){
check[i + j + 2*i*j] = true;
}
}
}
int prime_pair(int n){
int count = 0;
int temp;
int temp_2 = (n-2)/2;
bool check[temp_2 + 1];
memset(check, false, sizeof(check));
check_prime(check, temp_2);
for (int i=1; i <= temp_2; i++){
if (check[i] == false){
temp = 2*i + 1;
count += (temp / 2);
}
}
return count;
}
int main(){
int n = 10;
cout<<"Count of pairs with sum as a prime number and less than n are: " <<prime_pair(n);
return 0;
}輸出
如果我們執行以上程式碼，它將生成以下輸出 -
Count of pairs with sum as a prime number and less than n are: 6
285 次檢視
