是技术，更是艺术

一心编程，就没有解决不了的问题
posts - 9, comments - 11, trackbacks - 0, articles - 0

快速判断素数算法

Posted on 2010-07-16 21:40 李熙建 阅读(4190) 评论(3)  编辑 收藏 引用 所属分类: 算法
    引理：如果 a 是一个大于1的整数，而所有小于或等于根号 a  的素数都除不尽 a ，则 a 是素数。
理想的判断素数的方法应该是将所有小于或等于根号n的素数去除n，但是n是一个随机大于1的整数，小于这个数的平方根的素数表不好给定。下面介绍的方法，本意是动态的构建素数表，但是引入了很多冗余的除数。

代码：
bool prime (int num)
{
  if (num == 2 || num == 3 || num == 5)
    return true;
  if (num % 2 == 0 || num % 3 == 0 || num % 5 == 0 || num == 1)
    return false;

  unsigned long c = 7;
  int maxc = int (sqrt (num));
  while (c <= maxc)
    {
      if (num % c == 0)
        return false;
      c += 4;
      if (num % c == 0)
        return false;
      c += 2;
      if (num % c == 0)
        return false;
      c += 4;
      if (num % c == 0)
        return false;
      c += 2;
      if (num % c == 0)
        return false;
      c += 4;
      if (num % c == 0)
        return false;
      c += 6;
      if (num % c == 0)
        return false;
      c += 2;
      if (num % c == 0)
        return false;
      c += 6;
    }
  return true;
}

分析：
　　相对于sqrt(n)次除，上面的程序需要sqrt(n)*8/30次除，效率提升了15/4倍。
　　自然数n，我们假设小于n的素数数F(n),F(n)的分布规律为：当n趋向于无穷大时，F(n)/(x/logx) = 1;
        所以，动态的冗余度近似为：(sqrt(n)*4/15-x/logx)/sqrt(n)*4/15

其他更好的判断素数的算法，希望你能给我留言或者写在评论上，谢谢！

Feedback

# re: 快速判断素数算法  回复  更多评论   

2011-06-02 20:47 by 某W
这方法很强大~
谢谢~

# re: 快速判断素数算法  回复  更多评论   

2011-08-01 09:19 by 李熙建
@某W
谢谢，抛砖引玉而已，期待你提出更优秀的方法

# re: 快速判断素数算法  回复  更多评论   

2012-10-25 19:21 by aa
理论依据是什么？

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理