JR 精品文章 - Eratosthenes筛选法求素数的算法

首页 » 研究文集 » Java入门

搜索标题相关文章

发表评论

开始监控

加入收藏夹

Eratosthenes筛选法求素数的算法
xinglongbing 原创更新：2008-05-15 17:00:58 版本: 1.0

public class Sieve{
  public static void main(String[] args)
  {
     int max = 100;  //假设求100以内的素数
     boolean[] isPrime = new boolean[max+1];

     for(int i=0; i<=max; i++)
       isPrime[i]=true;

     isPrime[0]=isPrime[1]=false;  //1和0不是素数，所以将相应的
                                   //isPrime元素设置为false
     int n = (int)Math.ceil(Math.sqrt(max));

     for(int i=0; i<=n; i++)
     {
        if(isPrime[i])  //素数的整数倍不是素数，从而筛选掉所有不是素数的数
        {
           for(int j=2*i; j<=max; j=j+i)
              isPrime[j]=false;
         }
      }
      int largest;
      for(largest=max; !isPrime[largest]; largest--)
      {
        System.out.println(largest);
       }
   }

}

本篇文章对您是否有帮助？投票：是否投票结果：

作者其它文章：

作者全部文章

这个文章共有 0 条评论

上一篇文章

返回〔Java入门〕

下一篇文章