素数

2019-11-06 07:34:29

字体：大中小

来源：转载

供稿：网友

第一种

效率一般的：

输入50000计算出结果耗时4.033s

#include <iostream>using namespace std;int main(){ int n; cin >> n; cout << 2 <<endl; for(int i=3; i<=n; i++) { int j; for(j=3; j<i; j++) { if(i % j == 0) break; } if(j == i) cout << i <<endl; } return 0;}

第二种

略去了偶数的判断，并且只进行到根号下次

50000耗时3.018s

#include <iostream>#include <cstdio>using namespace std;int main(){ int n; cin >> n; cout << 2 << endl; for(int i=3; i<=n; i+=2)//偶数直接跳过不加判断 { int j; for( j=3; j<i; j+=2)//同样奇数的因子不可能是偶数，跳过 { if(i % j== 0)//存在因子就结束 break; if(j * j > i)//超过根号下次就结束 break; } if(j * j > i)//说明是第二个break掉的，说明不存在因子！ cout << i <<endl; } return 0;}

筛法求素数：

利用的是数组，空间换时间加快计算速度

#include <iostream>using namespace std;#define MAX 5000char isPRime[MAX + 10];int main(){ for(int i=2; i<=MAX; i++) isprime[i] = 1; for(int i=2; i<= MAX; i++) { if( isprime[i]) for(int j=i*2; j<= MAX; j+=2) isprime[j] = 0; } for(int i=2; i<MAX; i++) { if(isprime[i]) cout<< i << endl; } return 0;}

上一篇：js解析json报错

下一篇：NOIP2009