java使用筛选法求n以内的素数示例(java求素数)_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);
 }
}

时间: 2024-11-03 17:04:04

java使用筛选法求n以内的素数示例(java求素数)_java的相关文章

java struts2 action-方法调了两次不知道为什么,求大神帮助

问题描述 方法调了两次不知道为什么,求大神帮助 重定向到action,调用了两次action的方法,第一次我传的参数有值,第二次值变成了空,不知道为什么调用了两次方法,求大神帮助 这个是action,重定向是调用2次queryServiceGroup方法 <action name="addByIdGroup" method="addByIdGroup" class="customerDetailsAction" > <resul

素数筛选法的进一步升级

今天晚上,正在翻书的时候,想学习一下数论,结果看到了素数筛的一部分,浴室我就温习了一下素数筛选法的代码, 我突然发现在筛素数的时候可以把外层循环缩小到他的根号2倍,嘿嘿,有点高兴啊... 上代码:(其实跟以前的差不多就是一样的) /** 2015 - 09 - 25 Author: ITAK Motto: 今日的我要超越昨日的我,明日的我要胜过今日的我, 以创作出更好的代码为目标,不断地超越自己. **/ #include <iostream> #include <cstdio>

算法练习:Eratosthenes 筛选法

题目:Eratosthenes筛选法 内容: 求质数是一个很普遍的问题,通常不外乎用数去除,除到不尽时,给定的数就是质数.但是早在2000年前人们就知道了一个不必用除法而找出2~N的所有质数的方法.假设一个很神奇的筛子,可以给出一个数,例如i,这个筛子有办法把i所有的倍数去掉.请用这个方法求出2~N之间的所有质数.即Eratosthenes筛选法. 我的解法:上来没多想,打开vs2013就敲了起来,问题果然很简单,分分钟就超神..奥,不对就解决了!其实就是把后面可以用前面倍数表示的数去掉,因为偶

筛选法的C++实现_C 语言

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

GO语言求100以内的素数_Golang

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

求100以内的质数,值得一看

问题描述 刚才看了一个招聘求100以内的质数问题,去求职的要求差不多都在7500/M以上,更有甚者要到12000/M,其实算法有很多种我贴出自己的算法,要价:4500/public static void main(String[] args) {for(int i=1;i<=100;i++){int flag = 0;for(int j=1;j<=i;j++){if(i%j==0){flag++;}}if(flag>2){continue;}else {System.out.print

数据结构Java实现01----算法概述

[正文]      一.数据结构涵盖的内容:   二.算法的基本概念: 1.算法的概念: Algorithm,是对特定问题求解步骤的一种描述,它是指令的有限序列,其中每一条指令表示一个或者多个操作. 2.算法的特性: 有穷性:指令序列是有限的 确定性:每条语句的含义明确,无二义性 可行性:每条语句都应在有限的时间内完成 输入:零个或者多个输入 输出:一个或者多个输出 3.算法与程序的区别: 程序: (program)程序是软件开发人员根据用户需求开发的.用程序设计语言描述的适合计算机执行的指令(

Basic求10000以内的完美数_vb

完全数(Perfect number),又称完美数或完备数,是一些特殊的自然数.它所有的真因子(即除了自身以外的约数)的和(即因子函数),恰好等于它本身. Dim a as Integer,b as Integer,c as Integer For a = 1 To 10000 c = 0 For b = 1 To a \ 2 If a Mod b = 0 Then c = c + b Next b If a = c Then Print Str(a) Next a 另附上java版的代码 im

基于java的汽车整车仓储信息系统 怎么写啊毕业设计 没头绪...求解答

问题描述 基于java的汽车整车仓储信息系统 怎么写啊毕业设计 没头绪...求解答 我应该找什么资料~~╮(╯▽╰)╭..................................... 解决方案 胡乱抄一点交差,反正你什么都不会,现学现卖都来不及 http://wenku.baidu.com/link?url=Q0PTDWA-QGs0fV5Fhymyjy1uTKDKoatEoboQhWJKLL1yFTIteGba2OVffJdKZcuLNzUKtDnLCxejpRvxLbC0AypZRs