输入正整数n(n>=2),求不大于n的全部质数（素数）

质数（prime number）又称 素数，有无限个。质数定义为在大于1的自然数中，除了1和它本身以外不再有其他 因数的数称为质数。 比如： 2、3、5、7、11、13、17、19······ 2、3、5、7、11、13、17、19 #include <iostream> using namespace std; int main() { int n;

cin>>n; cout<<2<<endl; for(int i=3;i<=n;i+=2){//除了2之外，只需要遍历所有的奇数i是否满足条件即可 int k;//这里的k做测试使用 for(k=3;k<i;k+=2){ if(i%k==0) break; if(k*k>i) //当 k 大于 i的平方根后就不要再试了 break; } if(k*k>i) cout<<i<<endl;

}

return 0;

}

****************************************************** 方法二： //筛选法求素数 /* 利用空间（内存）去换时间  1.把所有的数初始化（假设）为素数 2.通过for遍历把每一个素数的倍数都标记为非素数 3.剩下的数就都是素数了  */ #include <iostream> using namespace std; #define max_num 100 char isPrimer[max_num+10]; int main(){ for (int i=2;i<=max_num;++i)//把所有的数初始化（假设）为素数 isPrimer[i] = 1; for (int i=2;i<=max_num;++i){//通过for遍历把每一个素数的倍数都标记为非素数 if(isPrimer[i]){ for(int j = 2*i;j<=max_num;j+=i)//依次为2,3,4,。。。的倍数，标记为非素数  isPrimer[j] = 0;//把素数i的倍数标记为非素数   } } for(int i=2;i<=max_num;++i){ if(isPrimer[i]){ cout <<i<<endl; } } return 0; }