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);
 }
}

赞 (0)

相关推荐

  • 筛选法的C++实现

    筛选法 介绍:筛选法又称筛法,是求不超过自然数N(N>1)的所有质数的一种方法.据说是古希腊的埃拉托斯特尼(Eratosthenes,约公元前274-194年)发明的,又称埃拉托斯特尼筛子. 具体做法是:先把N个自然数按次序排列起来.1不是质数,也不是合数,要划去.第二个数2是质数留下来,而把2后面所有能被2整除的数都划去.2后面第一个没划去的数是3,把3留下,再把3后面所有能被3整除的数都划去.3后面第一个没划去的数是5,把5留下,再把5后面所有能被5整除的数都划去.这样一直做下去,就会把不超

  • c++素数筛选法

    c++素数筛选法

    素数(又称质数):指在大于一的自然数中,只能被1和它自身整除的自然数: 素数筛选法是指一种非常规的素数判定方法,比较高效率: 原理:任何数的整数倍必定不是素数,大于二的偶数必定不是素数. 我们以找出100以内的素数为例,利用原理,我们可以首先排除偶数是素数,然后进一步判断奇数 实现将偶数标记为0,素数标记为1:(也可以用一个bool数组将偶数标记为false,奇数标记为true) 下面是全部代码 #include <iostream> #include <cmath> #defin

  • 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内存限制,当然有其他灵活方案可以绕过(比如位图法)   th

  • GO语言求100以内的素数

    本文实例讲述了GO语言筛选法求100以内的素数.分享给大家供大家参考.具体实现方法如下: 思路:找出一个非素数就把它挖掉,最后剩下就是素数. 下面就来欣赏一下go简洁的代码吧 目前不支持GO的代码插入,使用xml的代替一下. 复制代码 代码如下: package main import (     "fmt"     "math" ) func main() {     var i, j, n int     var a [101]int     for i = 1

  • python素数筛选法浅析

    python素数筛选法浅析

    原理: 素数,指在一个大于1的自然数中,除了1和此整数自身外,不能被其他自然数整除的数.在加密应用中起重要的位置,比如广为人知的RSA算法中,就是基于大整数的因式分解难题,寻找两个超大的素数然后相乘作为密钥的.一个比较常见的求素数的办法是埃拉托斯特尼筛法(the Sieve of Eratosthenes) ,说简单一点就是画表格,然后删表格,如图所示: 从2开始依次往后面数,如果当前数字一个素数,那么就将所有其倍数的数从表中删除或者标记,然后最终得到所有的素数. 有一个优化: 标记2和3的倍数

  • C/C++利用筛选法算素数的方法示例

    什么是求素数 素数指的是因子只有1和本身的数(1不是素数),求解素数在数学上应用非常广泛,而求解n以内的素数也是我们编程时常遇到的问题,在这个问题上,筛选法求解素数运行得非常快. i在2到n-1之间任取一个数,如果n能被整除则不是素数,否则就是素数 称筛法 筛选法又称筛法,是求不超过自然数N(N>1)的所有质数的一种方法.据说是古希腊的埃拉托斯特尼(Eratosthenes,约公元前274-194年)发明的,又称埃拉托斯特尼筛子. 具体做法是: 先把N个自然数按次序排列起来.1不是质数,也不是合

  • Ruby、PHP、Shell实现求50以内的素数

    ruby求50之内的素数的方法,感觉对比PHP和SHELL方法是最简单的,但SHELL中可以利用factor命令,而PHP中没有求素数的对应函数的,需要自己设计算法,三种方式大家对比学习下,应该还有更优更简单的方法的. 复制代码 代码如下: #encoding:utf-8 #求50以内的素数(注意数字中..与...的区别)   for i in 2..50 #1默认不为素数,所以从1-50范围内被排除     f=true #起始假定每个数都是素数     for p in 2...i #比自身

  • Java 驼峰命名法详解(必看篇)

    标识符: Java对各种变量.方法和类等要素命名时使用的字符序列称为标识符 凡是自己可以起名字的地方都叫标识符 定义合法标识符的规则: 由26个英文字母大小写,0-9,_或$组成 数字不可以开头 不可以使用关键字和保留字,但是能包括关键字和保留字 Java中严格区分大小写,长度无限制 标识符不能包括空格 取名尽量做到"见名知意" 关于使用中文,Oracle 官网给出的文档是这样描述的: An identifier is an unlimited-length sequence of J

  • python使用筛选法计算小于给定数字的所有素数

    本文实例为大家分享了python计算小于给定数字的所有素数的具体代码,供大家参考,具体内容如下 代码思路:首先列出指定范围内所有候选数字,然后从前往后依次选择一个数字去除以后面所有数字,能够被整除的肯定不是素数,把这些数字过滤掉,然后重复这个过程,直到选择的除数大于最大数字的平方根为止.代码主要演示内置函数filter()和切片的用法,实际上这个算法的效率并不是很高. def primes2(maxNumber): '''筛选法获取小于maxNumber的所有素数''' #待判断整数 lst =

  • python如何求100以内的素数

    方法一,用for循环来实现 num=[]; i=2 for i in range(2,100): j=2 for j in range(2,i): if(i%j==0): break else: num.append(i) print(num) 方法二,用函数来实现 import math def func_get_prime(n): return filter(lambda x: not [x%i for i in range(2, int(math.sqrt(x))+1) if x%i ==

随机推荐