首页 > 代码库 > 1007. 素数对猜想 (20)
1007. 素数对猜想 (20)
1007. 素数对猜想 (20) 让我们定义 dn 为:dn = pn+1 - pn,其中 pi 是第i个素数。显然有 d1=1 且对于n>1有 dn 是偶数。“素数对猜想”认为“存在无穷多对相邻且差为2的素数”。 现给定任意正整数N (< 105),请计算不超过N的满足猜想的素数对的个数。 输入格式:每个测试输入包含1个测试用例,给出正整数N。 输出格式:每个测试用例的输出占一行,不超过N的满足猜想的素数对的个数。 输入样例: 20 输出样例: 4
分析:题目很简单,主要是先把一定范围内的素数都求出来,然后用素数对的定义来统计一下所求范围内的素数对的数量就可以了。这里用了素数筛的算法来求素数。
#include <iostream> using namespace std; #define MAX_NUM 100000 #define MAX_PRIME 100000 int main() { //素数筛求素数 int prime[MAX_PRIME]; int tmp[MAX_NUM]; for(size_t i=0;i<MAX_NUM;i++) { tmp[i]=i; } for(size_t i=2;i<MAX_NUM/2;i++) { if(tmp[i]!=0) { for(size_t j=i+i;j<MAX_NUM;j+=i) { tmp[j]=0; } } } size_t index=1; for(size_t i=2;i<MAX_NUM;i++) { if(tmp[i]!=0) { prime[index]=tmp[i]; index++; } } int n; cin>>n; int ans=0; for(size_t i = 1;i<=index;i++) { if(prime[i+1]>n) break; if(prime[i+1]-prime[i]==2) { ans++; } } cout<<ans<<endl; return 0; }
1007. 素数对猜想 (20)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。