1007. 素数对猜想 (20)

曾经终败给现在 2022-08-23 00:51 199阅读 0赞

让我们定义 dn 为：dn = pn+1 \- pn，其中 pi 是第i个素数。显然有 d1=1 且对于n>1有 dn 是偶数。“素数对猜想”认为“存在无穷多对相邻且差为2的素数”。

现给定任意正整数N (< 105)，请计算不超过N的满足猜想的素数对的个数。

**输入格式：**每个测试输入包含1个测试用例，给出正整数N。

**输出格式：**每个测试用例的输出占一行，不超过N的满足猜想的素数对的个数。

输入样例：

20

输出样例：

4

分析:

简单来说就是先筛选出不超过N的所有素数, 两个相邻且差值为2的素数为一对素数对, 找出小于N的素数对的对数.

我们可以一次性筛选出N范围内的所有素数, 在对满足条件的素数对求和.

代码如下:

#include <iostream>
    #include <cstdio>
    #include <cstring>
    #include <algorithm>
    #include <cmath>
    using namespace std;
    int pri[100110] = {0};
    
    int prime(int a) {
    	if(a % 2 == 0 && a != 2) {
    		return 0;
    	}
    	for(int i = 3; i * i <= a; i++) {
    		if(a % i == 0) {
    			return 0;
    		}
    	}
    	return a != 1;
    }
    
    int main() {
    	int n;
    	int sum = 0, sub = 0;
    	cin >> n;
    	for (int i = 2; i <= 100010; i++) {	//一次性筛选出最大范围内的所有素数 
    		if(prime(i)) {
    			pri[sub++] = i;
    		}
    	}
    	for(int i = 1; pri[i] <= n; i++) {	//求出n以内的素数对的对数 
    		if(pri[i] - pri[i - 1] == 2) {
    			sum++;
    		}
    	}
    	cout << sum << endl;
    	return 0;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，199人围观）

还没有评论，来说两句吧...

相关阅读

相关 1007. 素数对猜想 (20)

让我们定义 dn 为：dn = pn+1 - pn，其中 pi 是第i个素数。显然有 d1=1 且对于n>1有 dn 是偶数。“素数对猜想”认为“存在无穷多对相邻且差为2的素数

Bertha 。/ 2022年08月23日 05:46/ 0 赞/ 163 阅读

相关 1007. 素数对猜想 (20)

让我们定义 dn 为：dn = pn+1 \- pn，其中 pi 是第i个素数。显然有 d1=1 且对于n>1有 dn 是偶数。“素数对猜想”认为“存在无穷多对相邻且差为2的素

曾经终败给现在/ 2022年08月23日 00:51/ 0 赞/ 200 阅读

相关 1007. 素数对猜想 (20) python篇

1007. 素数对猜想 (20) 时间限制 400 ms 内存限制 65536 kB 代码长度限制 8000 B 判题程序 Standar

约定不等于承诺〃/ 2022年07月03日 12:21/ 0 赞/ 211 阅读

相关 1007. 素数对猜想 (20)

让我们定义 dn 为：dn = pn+1 - pn，其中 pi 是第i个素数。显然有 d1=1 且对于n>1有 dn 是偶数。“素数对猜想”认为“存在无穷多对相邻且差为2的素数

Love The Way You Lie/ 2022年06月15日 10:13/ 0 赞/ 175 阅读

相关 JAVA-1007. 素数对猜想 (20)

让我们定义 dn 为：dn = pn+1 - pn，其中 pi 是第i个素数。显然有 d1=1 且对于n>1有 dn 是偶数。“素数对猜想”认为“存在无穷多对相邻且差为2的素数

￡神魔★判官ぃ/ 2022年06月12日 01:19/ 0 赞/ 163 阅读

相关 1007. 素数对猜想 (20)

让我们定义 dn 为：dn = pn+1 - pn，其中 pi 是第i个素数。显然有 d1=1 且对于n>1有 dn 是偶数。“素数对猜想”认为“存在无穷多对相邻且差为2的素数

野性酷女/ 2022年05月31日 13:57/ 0 赞/ 216 阅读

相关 1007. 素数对猜想 (20)

让我们定义 dn 为：dn = pn+1 \- pn，其中 pi 是第i个素数。显然有 d1=1 且对于n>1有 dn 是偶数。“素数对猜想”认为“存在无穷多对相邻且差为2的素

向右看齐/ 2022年05月27日 01:41/ 0 赞/ 188 阅读

相关 1007. 素数对猜想 (20)(java实现）

最开始提交的时候最后一组数据一直运行超时，相同代码换成c++也是，百思不得其解。。最后上课的时候想到判断是否是素数的时候，自己之前循环的num/2,但其实到100

超、凢脫俗/ 2022年02月27日 10:50/ 0 赞/ 212 阅读

相关 1007 素数对猜想 (20 分)

让我们定义dn为：dn=pn+1−pn，其中pi是第i个素数。显然有d1=1，且对于n>1有dn是偶数。“素数对猜想”认为“存在无穷多

阳光穿透心脏的1/2处/ 2021年12月19日 00:51/ 0 赞/ 247 阅读

相关 PAT 1007 素数对猜想 (20 分)（Java）

题目描述： ![在这里插入图片描述][20190822202034429.png] 输入格式: 输入在一行给出正整数N。输出格式: 在一行中输出

我不是女神ヾ/ 2021年09月23日 05:50/ 0 赞/ 279 阅读