好贷网好贷款

质数判断

发布时间:2016-12-4 22:32:09 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"质数判断",主要涉及到质数判断方面的内容,对于质数判断感兴趣的同学可以参考一下。

求质数: bool isPrime(int x) { int y = sqrt(x); for (;x % y != 0;y--) { ; } return y == 1; } 题目: 让我们定义 dn 为:dn = pn+1 - pn,其中 pi 是第i个素数。显然有 d1=1 且对于n>1有 dn 是偶数。“素数对猜想”认为“存在无穷多对相邻且差为2的素数”。 现给定任意正整数N (< 105),请计算不超过N的满足猜想的素数对的个数。 输入格式:每个测试输入包含1个测试用例,给出正整数N。 输出格式:每个测试用例的输出占一行,不超过N的满足猜想的素数对的个数。 输入样例: 20 输出样例: 4 数据大超时代码: #include <stdio.h> #include <math.h> bool isPrime(int x); int main(){ #ifdef ONLINE_JUDGE #else freopen("C:\\in.txt", "r", stdin); #endif int n; while(scanf ("%d", &n)!= EOF){ int prime[100000]; int i, cn=1; for(i=1; i<=n;i++){ if(isPrime(i)){ prime[cn++]=i; } }//全部质数 int ans=0; for(i=1;i<cn-1;i++){ if(prime[i+1]-prime[i] == 2) ans++; } printf("%d\n", ans); } return 0; } bool isPrime(int x) { if ( x == 2) { return true; } //超时原因:太多循环 int y = x/2; for (;x % y != 0;y--) { ; } return y == 1; } AC代码: #include <stdio.h> #include <math.h> bool isPrime(int x); int main(){ #ifdef ONLINE_JUDGE #else freopen("C:\\in.txt", "r", stdin); #endif int n; while(scanf ("%d", &n)!= EOF){ int prime[100000]; int i, cn=1; for(i=1; i<=n;i++){ if(isPrime(i)){ prime[cn++]=i; } }//全部质数 int ans=0; for(i=1;i<cn-1;i++){ if(prime[i+1]-prime[i] == 2) ans++; } printf("%d\n", ans); } return 0; } bool isPrime(int x) { int y = sqrt(x); for (;x % y != 0;y--) { ; } return y == 1; }

上一篇:在代码使用数据库SQLite的
下一篇:iOS 的 ASIHTTPRequest 类库简介和使用说明

相关文章

关键词: 质数判断

相关评论