文档章节

[java]埃拉托斯特尼筛法检定素数

tenght
 tenght
发布于 2016/04/13 16:12
字数 288
阅读 83
收藏 0

埃拉托斯特尼筛法,简称埃氏筛或爱氏筛,是一种由希腊数学家埃拉托斯特尼所提出的一种简单检定素数的算法。要得到自然数n以内的全部素数,必须把不大于根号n的所有素数的倍数剔除,剩下的就是素数。

给出要筛数值的范围n,找出以内的素数。先用2去筛,即把2留下,把2的倍数剔除掉;再用下一个质数,也就是3筛,把3留下,把3的倍数剔除掉;接下去用下一个质数5筛,把5留下,把5的倍数剔除掉;不断重复下去......。

java源码:

package test1.number;

public class Eratosthenes {
	public static void main(String[] args) {
		int max = 20; 
		try {
			max = Integer.parseInt(args[0]);
		} 
		catch (Exception e) {
		} 

		boolean[] isprime = new boolean[max + 1];

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

		isprime[0] = isprime[1] = 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("The largest prime less than or equal to " + max
				+ " is " + largest);
	}

}

运行结果:


本文转载自:http://blog.csdn.net/hadoop_/article/details/49883611

共有 人打赏支持
tenght
粉丝 0
博文 11
码字总数 0
作品 0
江北
程序员
私信 提问
10 Ruby One Liners to Impress Your Friends

1.列表中的每项乘2 p (1..10).map {|n| n*2} 2.对列表中的数字求和 p (1..1000).inject { |sum, n| sum + n } 或者使用自Ruby1.8.7以来Symbol#to_proc语法: p (1..1000).inject(&:+) 或者直接......

mathics
2013/01/12
0
4
10个让朋友对你刮目相看的CoffeeScript单行代码绝技

或许你已经看过了Marcus Kazmierczak的这篇在HN上颇受欢迎的“10个让朋友对你刮目相看的Scala单行代码绝技”了, 尽管我对Scala并不了解(Java也是),但是这看起来还真不错,于是我也有点手...

justjavac
2012/07/23
0
2
LeetCode - 204. Count Primes - 埃拉托斯特尼筛法 95.12% - (C++) - Sieve of Eratosthenes

原题 原题链接 Description: Count the number of prime numbers less than a non-negative number, n. 计算小于非负数n的素数个数。 思路 这题用埃拉托斯特尼筛法来做效果比较好,普通的方法...

rgvb178
2017/01/10
0
0
python学习--埃拉托斯特尼筛法求素数

埃拉托斯特尼筛法: 给出要筛数值的范围n,找出以内的素数。先用2去筛,即把2留下,把2的倍数剔除掉;再用下一个质数,也就是3筛,把3留下,把3的倍数剔除掉;接下去用下一个质数5筛,把5留下...

秦风楚韵
2012/04/18
0
0
LeetCode:Count Primes - 统计质数数量

1、题目名称 Count Primes(统计质数数量) 2、题目地址 https://leetcode.com/problems/count-primes/ 3、题目内容 英文:Count the number of prime numbers less than a non-negative nu......

北风其凉
2015/09/06
765
0

没有更多内容

加载失败,请刷新页面

加载更多

Spring学习记录

Java类定义配置 @Configuration //标记为配置类@ComponentScan //标记为扫描当前包及子包所有标记为@Component的类@ComponentScan(basePackageClasses = {接口.class,...}) //标记为扫描当...

CHONGCHEN
今天
1
0
如何开发一款以太坊(安卓)钱包系列2 - 导入账号及账号管理

这是如何开发一款以太坊(安卓)钱包系列第2篇,如何导入账号。有时用户可能已经有一个账号,这篇文章接来介绍下,如何实现导入用户已经存在的账号。 导入账号预备知识 从用户需求上来讲,导...

Tiny熊
今天
3
0
intellJ IDEA搭建java+selenium自动化环境(maven,selenium,testng)

1.安装jdk1.8; 2.安装intellJ; 3.安装maven; 3.1 如果是单前用户,配置用户环境变量即可,如果是多用户,则需配置系统环境变量,变量名为MAVEN_HOME,赋值D:\Application\maven,往path中...

不最醉不龟归
今天
4
0
聊聊ShenandoahGC的Brooks Pointers

序 本文主要研究一下ShenandoahGC的Brooks Pointers Shenandoah Shenandoah面向low-pause-time的垃圾收集器,它的GC cycle主要有 Snapshot-at-the-beginning concurrent mark包括Init Mark(P......

go4it
昨天
4
0
Makefile通用编写规则

#简单实用的Makefile模板: objs := a.o b.o test:$(objs) gcc -o test $^ # .a.o.d .b.o.d dep_files := $(foreach f,$(objs),.$(f).d) dep_files := $(wildcard $(dep_files)) ifneq ($(d......

shzwork
昨天
3
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部