java使用筛选法求n以内的素数示例(java求素数)

软件编程 java 分类:[default] 更新日期: 2016-04-05
这篇文章主要介绍了java使用筛选法求n以内的素数示例java求素数,需要的朋友可以参考下

代码如下:

/**
 * @author jxqlovedn
 * 埃拉托斯特尼素数筛选法,请参考:http://zh.wikipedia.org/zh-cn/埃拉托斯特尼筛法
 */
public class AratosternyAlgorithm {
 public static void getPrimes(int n) {
  if(n < 2 || n > 1000000)   // 之所以限制最大值为100万,是因为JVM内存限制,当然有其他灵活方案可以绕过(比如位图法)
   throw new IllegalArgumentException("输入参数n错误!");
  int[] array = new int[n];   // 假设初始所有数都是素数,且某个数是素数,则其值为0;比如第一个数为素数那么array[0]为0
  array[0] = 1;   // 0不是素数
  array[1] = 1;   // 1不是素数
  // 下面是筛选核心过程
  for(int i = 2; i < Math.sqrt(n);i++) {   // 从最小素数2开始
   if(array[i] == 0) {
    for(int j = i*i; j < n; j += i) {
     array[j] = 1;   // 标识该位置为非素数
    }
   }
  }
  // 打印n以内的所有素数,每排10个输出
  System.out.println(n + "以内的素数如下: ");
  int count = 0;        // 当前已经输出的素数个数
  int rowLength = 10;   // 每行输出的素数个数
  for(int i = 0; i < array.length; i++) {
   if(array[i] == 0) {
    if(count % rowLength == 0 && count != 0) {
     System.out.println();
    }
    count++;
    System.out.print(i + "\t");
   }
  }
 }
 public static void main(String[] args) {
  getPrimes(99999);
 }
}


> 本站内容系网友提交或本网编辑转载,其目的在于传递更多信息,并不代表本网赞同其观点和对其真实性负责。如涉及作品内容、版权和其它问题,请及时与本网联系,我们将在第一时间删除内容!

相关文章
  • Web2.0编程思想:16条法则
    1.在你开始之前,先定一个简单的目标.无论你是一个Web 2.0应用的创建者还是用户,请清晰的构思你的目标.就像"我需要保存一个书签"或者"我准备帮助人们创建可编辑的.共享的页面"这样的目标,让你保持最基础的需求.很多Web 2.0应用的最初吸引之处就是它的简单,避免并隐藏了那些多余的复杂性.站在创建者的立场,可以想象 ...
  • Flex中对表格某列的值进行数字格式化并求百分比添加%
    Flex中对表格某列的值进行数字格式化并求百分比添加%
    需要对表格中某列的数值进行格式化,对该数值乘以100,并保留两位小数,添加"%"下面同实例来实现下1.问题背景 一般的,需要对表格中某列的数值进行格式化,对该数值乘以100,并保留两位小数,添加"%" 2.实现实例 <?xml version="1.0" encoding="utf- ...
  • php项目开发中用到的快速排序算法分析
    这篇文章主要介绍了php项目开发中用到的快速排序算法,结合实例形式详细分析了php快速排序的原理与使用方法,需要的朋友可以参考下本文实例讲述了php项目开发中用到的快速排序算法.分享给大家供大家参考,具体如下: 实际上在,做web开发,比较少遇到使用一些算法之类的,毕竟不是做搜索引擎,也不是写底层(比如写个类似于mysql这样的数据库,里面需要自己实现排序算 ...
  • 正则表达式性能优化方法高效正则表达式书写
    正则表达式性能优化方法高效正则表达式书写
    这里说的正则表达式优化,主要是针对目前常用的NFA模式正则表达式这里说的正则表达式优化,主要是针对目前常用的NFA模式正则表达式,详细可以参考:正则表达式匹配解析过程探讨分析(正则表达式匹配原理).从上面例子,我们可以推断出,影响NFA类正则表达式(常见语言:GNU Emacs,Java,ergp,less,more,.NET语言, PCRE library ...
  • 将xml文件作为一个小的数据库,进行学生的增删改查的简单实例
    下面小编就为大家带来一篇将xml文件作为一个小的数据库,进行学生的增删改查的简单实例.小编觉得挺不错的,现在就分享给大家,也给大家做个参考.一起跟随小编过来看看吧1.xml文件: <?xml version="1.0" encoding="UTF-8"?><Students> <stude ...
  • JavaWeb实现图形报表折线图的方法
    这篇文章主要介绍了JavaWeb实现图形报表折线图的方法,涉及JSP包的引用.图形操作.配置文件设置及字符串操作技巧,需要的朋友可以参考下本文实例讲述了JavaWeb实现图形报表折线图的方法.分享给大家供大家参考,具体如下: 步骤说明: 1. 导入log4j.jar,jfreechart-0.9.18.jar,jdom.jar,jcommon-0.9.3.j ...
猜你喜欢