解题思路:
注意事项:
参考代码:
#include<iostream>
#include<stdio.h>
#include<string.h>
using namespace std;
int main()
{
int a,b,i,j,m,n;
cin>>n;
cout<<2<<endl; //2是素数直接输出
for(i=3;i<=n;i++)
{
a=1;
for(j=2;j<i;j++) //出去1从2开始并小于自身
{
if(i%j==0) //不满足除自身和一外有因数,a=0表示不是
{
a=0;
break; //跳出内循环,表示此时i不是素数,开始下一个数的判断
}
}
if(a!=0) //a=0,不是,a=1是
cout<<i<<endl;
}
}
/***************************************************************/
算法优化
//当n很大时,一下思路仅供参考
/* 根据素数定义,对于给定的正素数n,n是素数的条件是不能被 2,3……n-1整除。这种求素数的方法,当n很大,计算量也很大,效率很低。实际上,任何大于n/2的值不可能被n整除,因此n是素数的条件可以被简化为
不能被2,3...n/2整除。进一步可得n是素数的条件是不能被2,3...根号n整除。
int limit=sqrt(n)+1; //平方根是浮点数,比如25开根号可能是4.9999 所以
//i可能无法判断5这种可能,所以这里加一
举个例子:16的因数有:1,2,4,8,16,1与16配对,2与8配对,4是16的算术不方根,所以只能与自身配对,从这就可以看出来,一个数只要不能被不超过它的算术平方根整除,那么后面的数也一定不可能有它的因数了。
*/
0.0分
0 人评分
C语言程序设计教程(第三版)课后习题7.5 (C语言代码)浏览:546 |
C语言程序设计教程(第三版)课后习题9.10 (C语言代码)浏览:605 |
C语言训练-排序问题<2> (C++代码)浏览:887 |
用筛法求之N内的素数。 (C语言代码)浏览:1262 |
愚蠢的摄影师 (C++代码)浏览:938 |
简单的a+b (C语言代码)浏览:952 |
字符串的输入输出处理 (C语言代码)浏览:1016 |
C语言程序设计教程(第三版)课后习题11.5 (C语言代码)浏览:1000 |
C语言程序设计教程(第三版)课后习题10.3 (C语言代码)浏览:840 |
C语言程序设计教程(第三版)课后习题1.5 (C语言代码)浏览:546 |