数据结构
网络
关系型数据库管理系统
操作系统
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 次查看
