1.素数的定义
只能被1和它自己整除的自然数称为素数，特别规定1不属于素数。
2.求法
(1)根据素数的定义，很明显，如果一个数是素数<==>它的因子只包含1和它本身。
因此可以根据判别某个数的因子的方法来判断其是否是素数。
- int isprime(int n)
- {
- int i;
- for(i=2;i<=(int)sqrt((double)n);i++)
- {
- if(n%i==0) //如果n存在其它因子,则必定不是素数
- {
- return0;
- }
- }
- return1;
- }
(2)但是如果要求求出1000000以内的所有素数，上面的方法效率就很低，因此通常采用筛选法去求素数。 筛选法：对于一个数n，如果是素数，那么2*n，3*n，4*n，必定不是素数。 - bool isprime[1000001];
- int prime[80000];
- int num=0;
- void getPrime() //用筛选法求算素数
- {
- int i,j;
- for(i=0;i<1000001;i++)
- {
- if(i%2!=0)
- isprime[i]=true;
- else
- isprime[i] = false;
- }
- for(i=2;i<=1000;i++) //如果isprime[i]==true,即i是素数，那么i，2*i，3*i必定不是素数
- {
- for(j=i+i;j<=1000000;j+=i)
- {
- if(isprime[i]==true)
- isprime[j]=false;
- }
- }
- for(i=2;i<1000001;i++)
- {
- if(isprime[i]==true)
- {
- prime[num++]=i;
- }
- }
- }
作者：Matrix海子
出处：http://www.cnblogs.com/dolphin0520/
本博客中未标明转载的**归作者Matrix海子和博客园共有，欢迎转载，但未经作者同意必须保留此段声明，且在**页面明显位置给出原文连接，否则保留追究法律责任的权利。
| 
楼主
