素数
除了1和本身之外,不能被其他数整除的一类数
1.对给定的正整数n,对任意的正整数a(1<a<n)都有n%a!=0成立
2.一既不是素数也不是合数
3.n与2到n-1中每一个数相除来测试是否能否整除,但是O(n)复杂度有点大,为了优化,可以通过平方来减少次数
#include<iostream> #include<math.h> using namespace std; int prime[10000]; int pNum=0; bool p[10000]={0}; bool isPrime(int n){//判断n是否为素数 if(n<=1){ return false; } for(int i=2;i*i<=n;i++){ if(n%i==0){ return false; } } return true; } void Find_Prime(int n){//求素数表 for(int i=1;i<=n;i++){ if(isPrime(i)==true){ prime[pNum++]=i; p[i]=true; } } } int main(){ int n; while(cin>>n){ Find_Prime(n); for(int i=0;i<pNum;i++){ cout<<prime[i]<<" "; } if(pNum==0){//如果没有素数则输出-1 cout<<"-1"; } cout<<endl; } return 0; }
法二:
素数筛法
对数组从小到大开始,从第一位数开始,将这个数的倍数全部设为合数,然后找到下一位没有被设为何叔的数组下标,从这位数字继续将这个数的倍数全部设为合数,直到最后一个数字。O(nloglogn)
#include<iostream> using namespace std; int prime[10000]; int pNum=0; bool p[10000]={0}; void Find_Prime(int n){//求素数表 for(int i=2;i<=n;i++){ if(p[i]==false){ prime[pNum++]=i; for(int j=i+i;j<=n;j=j+i){//每次增加i,对i的倍数进行检查 p[j]=true; } } } } int main(){ int n; while(cin>>n){ Find_Prime(n); for(int i=0;i<pNum;i++){ cout<<prime[i]<<" "; } if(pNum==0){//如果没有素数则输出-1 cout<<"-1"; } cout<<endl; } return 0; }