输入一个求出以内的质数

《输入一个求出以内的质数》由会员分享，可在线阅读，更多相关《输入一个求出以内的质数（2页珍藏版）》请在金锄头文库上搜索。

1、我们先来分析一下，一个整数n如果是素数那它有什么特征？哦，它只能够被1还有它本身整除。所以除了1和n之外，其它的从2到n-1之间的整数，都必须不能整除n。那么我们就取一个n，造一个循环语句，判断从2到n-1之间的整数中，有没有能整除n的，有的话，哪怕只有一个，那n都不是素数。懂了吗？ 也许有的朋友已经开始骂我笨了，没错，上面那个方法，确实有许多可以偷懒的地方，编程的一个大原则就是能有多懒就要多懒（当然是要在正确的前提下了。）还是不要叫懒吧，叫它优化，一个程序的效率，就取决于算法的好坏，一个好的高效率的算法和一个低效率的算法，所需要的时间相差很大，有时是一个只要几秒而另一个却要几千年。还是上面的

2、例子：1、比n的平方根还大的整数，当然不能整除n。所以，这一部分我们不用管它。2、如果从2到int (sqrt(n)之间有一个数能整除n，那我们对n的判断就应该结束了而没必要再判断下面的数。3、你想一下如果一个数不能被2整除，那它还能够被4，被6，被8等等的2的倍数整除吗？当然不能。所以，我们又得出了一个结论。只要一个数n不能被所有的从2到int(sqrt(n)之间的素数整除，那它就一定是素数。这样，我们就把这个问题的算法，优化了不少。总结一下，枚举就是在全集中的元素一个一个拿出来试，有点象小孩数糖果，由于它的运算量相对较大，所以，我们应该注意尽可能地限制一些无谓运算的出现，这是搜索所要求的最重要的技巧。Input 输入一个N，求出 (0, N 以内的质数。输入数据只有一个数N ,范围： N=0 & N=30000Output 输出(0, N 以内所有的质数，一个数占一行。Sample Input 10Sample Output 2357#includeint main()int i,n,t,m;while(scanf(%d,&n)!=EOF) for(i=2;i=n;i+) m=i-1;for(t=2;t=m;t+)if(i%t=0)break;if(i=t)printf(%dn,i);return 0;