素数的求法-阿里云开发者社区

开发者社区> 云计算> 正文
登录阅读全文

素数的求法

简介:

素数的求法
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;
}
}
}
复制代码

本文转载自海 子博客园博客,原文链接:http://www.cnblogs.com/dolphin0520/archive/2011/04/17/2019021.html如需转载自行联系原作者

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

分享:
云计算
使用钉钉扫一扫加入圈子
+ 订阅

时时分享云计算技术内容,助您降低 IT 成本,提升运维效率,使您更专注于核心业务创新。

其他文章