大家好,小百来为大家解答以上的问题。C语言判断素数，c语言判断素数这个很多人还不知道,现在让我们一起来看看吧！

1、基本思想：把m作为被除数，将2—INT（ ）作为除数，如果都除不尽，m就是素数，否则就不是。

2、可用以下程序段实现：void main(){ int m,i,k;printf("please input a number:");scanf("%d",&m);k=sqrt(m);for(i=2;i=k)printf("该数是素数");elseprintf("该数不是素数");}将其写成一函数,若为素数返回1，不是则返回0int prime( m%){int i,k;k=sqrt(m);for(i=2;i

3、剩下的数中选择最小的数是素数，然后去掉它的倍数。

4、依次类推，直到筛子为空时结束。

5、如有：1 2 3 4 5 6 7 8 9 1011 12 13 14 15 16 17 18 19 2021 22 23 24 25 26 27 28 29 301不是素数，去掉。

6、剩下的数中2最小，是素数，去掉2的倍数，余下的数是：3 5 7 9 11 13 15 17 19 21 23 25 27 29剩下的数中3最小，是素数，去掉3的倍数，如此下去直到所有的数都被筛完，求出的素数为：2 3 5 7 11 13 17 19 23 29二、C++实现算法一：令A为素数，则A*N（N>1;N为自然数）都不是素数。

7、#define range 2000bool IsPrime[range+1];/*set函数确定i是否为素数，结果储存在IsPrime[i]中，此函数在DEV C++中测试通过*/void set(bool IsPrime[]){int i,j;for(i=0;i<=range;++i)IsPrime[i]=true;IsPrime[0]=IsPrime[1]=false;for(i=2;i<=range;++i){if(IsPrime[i]){for(j=2*i;j<=range;j+=i)IsPrime[j]=false;}}}2、说明：解决这个问题的诀窍是如何安排删除的次序，使得每一个非质数都只被删除一次。

8、 中学时学过一个因式分解定理，他说任何一个非质（合）数都可以分解成质数的连乘积。

9、例如，16=2^4，18=2 * 3^2，691488=2^5 * 3^2 * 7^4等。

10、如果把因式分解中最小质数写在最左边，有16=2^4，18=2*9,691488=2^5 * 21609,；换句话说，把合数N写成N=p^k * q，此时q当然是大于p的，因为p是因式分解中最小的质数。

11、由于因式分解的唯一性，任何一个合数N，写成N=p^k * q;的方式也是唯一的。

12、由于q>=p的关系，因此在删除非质数时，如果已知p是质数，可以先删除p^2,p^3,p^4,... ，再删除pq,p^2*q,p^3*q,...,（q是比p大而没有被删除的数），一直到pq>N为止。

13、因为每个非质数都只被删除一次，可想而知，这个程序的速度一定相当快。

14、依据Gries与Misra的文章，线性的时间，也就是与N成正比的时间就足够了（此时要找出2N的质数）。

15、 代码如下：#include#includeusing namespace std;int main(){int N; cin>>N;int *Location=new int[N+1];for(int i=0;i!=N+1;++i)Location[i]=i;Location[1]=0; //筛除部分 int p,q,end;end=sqrt((double)N)+1;for(p=2;p!=end;++p){if(Location[p]){for(q=p;p*q<=N;++q){for(int k=p*q;k<=N;k*=p)Location[k]=0;}}}int m=0;for(int i=1;i!=N+1;++i){if(Location[i]!=0){cout<

16、以上两种算法在小数据下速度几乎相同。

17、参考资料：百度百科-筛法求素数。

本文到此分享完毕，希望对大家有所帮助。