Java中的素数生成算法- Eratosthenes的筛选实例

良好的数据结构和算法知识是成为一个更好的程序员的第一步。为了延续这个传统,今天我将分享一个有趣的算法,Eratosthenes算法的Sieve,它可以用来生成质数直到给定的数字。在很多情况下,你需要生成指定整数的所有素数,而最常用于生成素数的算法是Eratosthenes算法的 Sieve。但是很少有开发人员知道这个算法,特别是Java程序员,这主要是因为没有进行足够的竞争性编程。

Eratosthenes Sieve of Eratosthenes是一种古希腊算法,用于查找给定数字之前的所有素数,以希腊著名数学家Eratosthenes的名字命名。他是第一个计算地球周长的人,也因研究历法闰年而闻名。

素数是一个整数,它可以被1整除也可以像2 3 5这样被自身整除,而不能被任何正整数整除。

换句话说,素数不具有1或其自身的因子。可以使用此算法生成从1到100或任意最大值的素数。

在本文中,不仅将学习Eratosthenes Sieve算法的工作原理,还将使用该算法生成素数,并验证生成的所有数是否都是素数。

Eratosthenes算法的Sieve如何工作

Eratosthenes算法的Sieve非常简单。可以通过指定的整数创建大于1的数组,以便该数组的索引表示存储在其上的实际整数。然后从2开始,因为0和1不被认为是素数。

素数要么能被1整除要么能被自身整除,它没有其他因数。因为2是素数,我们把它标记为素数然后划掉所有倍数因为它们不是素数,为什么?因为素数不具有除1之外的任何因子,并且如果数字是2的倍数,则意味着它可以被2整除,因此不是素数。

为了越过所有乘以2的数字,我们只是将数组计数器跳过2,这意味着2,4,6,8都是2的倍数,它们将被交叉。数组中的下一个数字是3,现在3也不能被任何人整除,因此它是素数,我们将其标记为素数,并再次划掉所有3的倍数,因为它们不是素数。

为了超过3的倍数,我们跳过数组计数器3,这意味着3,9,12,15都是交叉的。现在,下一个数字是4但它已经越过,因为它是2的倍数所以我们跳到下一个数字是5。

5是素数,所以我们将它标记为素数,并将所有5的倍数交叉,因为它们不会是素数,它们可以被5整除。为了跨越5的所有倍数,我们只增加数组计数器按5,所以数字如10,15,20,25将被划掉。

我们继续这个过程,直到达到给定数字的平方根,因为数组中的每个倍数都有一个小于或等于给定数字的平方根的素数因子,所以我们不必交叉出倍数大于该根的数字 例如,为了找到1到100之间的所有素数,它足以检查到10。

Java中Eratosthenes算法实现的筛选

这是我们的Java程序,它使用Java编程语言中的Eratosthenes算法Sieve实现生成素数的逻辑:

import org.junit.Test;

import static org.junit.Assert.*;

/**

*此类使用以下内容生成达到给定限制的素数

* Eratosthenes算法筛选。在这个算法中,我们创建了

*从2开始的整数数组,然后找到第一个未交叉的整数

*整数,并将其全部交叉。重复该过程

*直到阵列中没有多个倍数。

*/

public class PrimeNumberGenerator {

private enum Marker{

CROSSED, UNCROSSED;

}

private static Marker[] crossedOut;

private static int[] primes;

public static int[] generatePrimeNumbersUpto(int limit){

if(limit < 2){

return new int[0];

}else{

uncrossIntegerUpto(limit);

crossOutMultiples();

putUncrossedIntegersIntoPrimes();

return primes;

}

}

private static void uncrossIntegerUpto(int limit) {

crossedOut = new Marker[limit + 1];

for(int i = 2; i

crossedOut[i] = Marker.UNCROSSED;

}

}

private static void crossOutMultiples() {

int iterationLimit = determineIterationLimit();

for (int i = 2; i<= iterationLimit; i++){

if(notCrossed(i)){

crossOutMultipleOf(i);

}

}

}

private static int determineIterationLimit() {

//数组中的每个倍数都有一个素数因子

//小于或等于平方根

//数组大小,我们不需要越过

//大于根的倍数。

double iterationLimit = Math.sqrt(crossedOut.length);

return (int) iterationLimit;

}

private static boolean notCrossed(int i) {

return crossedOut[i] == Marker.UNCROSSED;

}

private static void crossOutMultipleOf(int i) {

for(int multiple = 2*i;

multiple < crossedOut.length;

multiple += i){

crossedOut[multiple] = Marker.CROSSED;

}

}

private static void putUncrossedIntegersIntoPrimes() {

primes = new int[numberOfUncrossedIntegers()];

for(int j = 0, i = 2; i

if(notCrossed(i)){

primes[j++] = i;

}

}

}

private static int numberOfUncrossedIntegers() {

int count = 0;

for(int i = 2; i

if(notCrossed(i)){

count++;

}

}

return count;

}

}

在Java中检查Prime数的单元测试

下面是一些单元测试,用于检查我们的程序是否正常工作

import static org.junit.Assert.*;

import org.junit.Test;

/** * Junit测试用例来测试我们的Eratosthenes Sieve算法

* 用于生成一个给定整数的素数

* */

public class PrimeNumberGeneratorTest{

public PrimeNumberGeneratorTest(){

System.out.println("Generator prime numbers using"

+ " Sieve of Eratosthenes algorithm");

}

@Test

public void testPrimes(){

int[]primeUptoZero = PrimeNumberGenerator.generatePrimeNumbersUpto(0);

assertEquals(0, primeUptoZero.length);

int[] primeUptoTwo = PrimeNumberGenerator.generatePrimeNumbersUpto(2); assertEquals(1, primeUptoTwo.length);

assertEquals(2, primeUptoTwo[0]);

int[] primeUptoThree = PrimeNumberGenerator.generatePrimeNumbersUpto(3); assertEquals(2, primeUptoThree.length);

assertEquals(2, primeUptoThree[0]);

assertEquals(3, primeUptoThree[1]);

int[]primeUptoHundred=PrimeNumberGenerator.generatePrimeNumbersUpto(100);

assertEquals(25, primeUptoHundred.length);

assertEquals(97, primeUptoHundred[24]);

}

@Test

public void testExhaustive(){

for(int i = 2; i<700; i++){    verifyPrimeList(PrimeNumberGenerator.generatePrimeNumbersUpto(i));

}

}

private void verifyPrimeList(int[] listOfPrimes) {

for(int i = 0; i

verifyPrime(listOfPrimes[i]);

}

}

private void verifyPrime(int number) {

for (int factor = 2; factor < number; factor++){

assertTrue(number%factor != 0);

}

}

}

这是我们单元测试的结果,全部通过了

这就是如何使用Sieve of Eratosthenes算法生成高达指定整数的素数。这是生成大量素数的非常有效的算法,可用于解决需要素数数组的复杂编程问题。

©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 205,386评论 6 479
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 87,939评论 2 381
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 151,851评论 0 341
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 54,953评论 1 278
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 63,971评论 5 369
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 48,784评论 1 283
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 38,126评论 3 399
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 36,765评论 0 258
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 43,148评论 1 300
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 35,744评论 2 323
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 37,858评论 1 333
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 33,479评论 4 322
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 39,080评论 3 307
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 30,053评论 0 19
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 31,278评论 1 260
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 45,245评论 2 352
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 42,590评论 2 343

推荐阅读更多精彩内容

  • 【程序1】 题目:古典问题:有一对兔子,从出生后第3个月起每个月都生一对兔子,小兔子长到第三个月后每个月又生一对兔...
    开心的锣鼓阅读 3,307评论 0 9
  • 【程序1】 题目:古典问题:有一对兔子,从出生后第3个月起每个月都生一对兔子,小兔子长到第三个月后每个月又生一...
    阿里高级软件架构师阅读 3,277评论 0 19
  • Java经典问题算法大全 /*【程序1】 题目:古典问题:有一对兔子,从出生后第3个月起每个月都生一对兔子,小兔子...
    赵宇_阿特奇阅读 1,841评论 0 2
  • 50道经典Java编程练习题,将数学思维运用到编程中来。抱歉哈找不到文章的原贴了,有冒犯的麻烦知会声哈~ 1.指数...
    OSET我要编程阅读 6,943评论 0 9
  • 【程序1】 题目:古典问题:有一对兔子,从出生后第3个月起每个月都生一对兔子,小兔子长到第三个月后每个月又生一对兔...
    叶总韩阅读 5,126评论 0 41