是否有人可以解释这是如何实现的作品？另外，可以把它变得更好？怎么样？ [英] Can someone please explain how this implementation works? Also, can it be made better? How?

问题描述

public class Main { 
    public static void main(String args []){ 
        long numberOfPrimes = 0; //Initialises variable numberOfPrimes to 0 (same for all other variables)
        int number = 1; 
        int maxLimit = 10000000; 
        boolean[] sieve = new boolean[maxLimit]; //creates new boolean array called sieve and allocates space on the
                                                //stack for this array which has maxLimit spaces in it 
        for ( int i = 2; i < maxLimit; i++ ) { //for statement cycling from 2 to 10000000, does not execute the rest
                                              //of the block if the boolean value in the array is true 
            if ( sieve[i] == true ) continue; 

            numberOfPrimes++; //otherwise it increments the number of prime numbers found

            if ( numberOfPrimes == 10001 ) {  //if 10001st prime number is found, break from loop
                number = i; 
                break; 
            } 

            for ( int j = i+i; j < maxLimit; j += i ) //do not understand the point of this loop logically
                sieve[j] = true;                      //testing if the value in the array is true again?
        } 
        System.out.println("10001st prime: "+ number); 
    } 
    }

我真的不明白是怎么回事这项计划，并希望有人可以解释给我呢？我有评论的具体线路造成我的麻烦/我的理解线在做。非常感谢所有帮助！ ：）

I don't really understand what is going on in this program and was hoping somebody could explain it to me? I have commented the specific lines causing me trouble/what I understand lines to be doing. Thank you very much for all the help! :)

推荐答案

是的，这是基本的埃拉托色尼筛的实施。有相当多的方法，使您可以改善它，但我们去了的基本原则第一。

Yes, this is your basic implementation of Eratosthenes' Sieve. There are quite a few ways in which you can improve it, but let's go over the basic principle first.

你在做什么是创造布尔值的数组。重新$ P $阵列中的索引psents我们正在测试，看它是否是一个素或数量不限。

What you are doing is creating an array of boolean values. The INDEX in the array represents the number which we are testing to see if it is a prime or not.

现在你要开始检查每个号码，看它是否是一个素数。首先，一个主要的定义是只有自己，没有分馏1整除的所有数字。

Now you are going to start checking each number to see if it is a prime. First off, the definition of a prime is "all numbers divisible ONLY by itself and 1 without fractioning".

for ( int i = 2; i < maxLimit; i++ )

您开始与INDEX 2（3号），因为这取决于你的定义，1和2是总是素数。 （有些定义说，1不是素数）。

You start with the INDEX 2 (the number 3) because depending on your definition, 1 and 2 are always prime. (Some definitions say 1 is not a prime).

if ( sieve[i] == true ) continue;

如果一个已被标记为一个非黄金previously，我们也懒得与当前迭代。

If a number has been marked as a non-prime previously, we don't bother with the current iteration.

numberOfPrimes++;

        if ( numberOfPrimes == 10001 ) {
            number = i; 
            break; 
        }

如果我们在目前指数还没有被标记为一个素数，它必须是一个，所以我们增加我们发现的素数的数量。下一条code我假设是，其中规定，如果10001素数已被发现，程序必须退出程序的要求的一部分。这部分可以省略，如果你真的想检查素数最多可代替定义为质数的特定数量的最大数量。

If the INDEX we are at currently has not been marked as being a prime, it has to be one, so we increment the number of primes we have found. The next piece of code I'm assuming is part of the requirements of the program which states that if 10001 primes have been found, the program must exit. That part can be left out if you actually want to check for primes up to the maximum number defined in stead of for a specific number of primes.

for ( int j = i+i; j < maxLimit; j += i )
            sieve[j] = true;

这就是筛的实际魔术开始。从总理的定义，一些不能是首要，如果它是整除以外的本身和1。因此，对于任何新的号码，我们发现这是一个素数，我们可以标记所有它的因素不是素数。例如，在第一次迭代循环，我们先从3.由于筛[2]是假的（以前没有访问过），这是一个主要的（和3是一个最好的！）。然后，3所有其他因素不能被素数。以上提到的for循环会遍历整个筛，标志着3的因素为假。这样循环会做：筛[5] =真;筛[8] =真......直到筛的端

This is where the actual magic of the sieve starts. From the definition of a prime, a number cannot be a prime if it is divisible by anything other than itself and 1. Therefore, for any new number we find that is a prime, we can mark all it's factors as NOT being prime. For example, the first iteration of the for loop, we start with 3. Because sieve[2] is false (have not visited before), it is a prime (AND 3 IS A PRIME!). Then, all other factors of 3 CANNOT be primes. The above mentioned for loop goes through the entire sieve and marks all factors of 3 as false. So that loop will do: sieve[5] = true; sieve[8] = true ... up until the end of the sieve.

现在，当你到达的第一个数字大于最初定义的最大，你可以肯定，任何数字，有一个因素已被标记为不是素数。你最终什么是布尔数组，其中每个索引标记为假，再presents一个素数。

Now, when you reach the first number greater than the maximum defined initially, you can be certain that any number that has a factor has been marked as not being a prime. What you end up with is a boolean array, where each index marked as false, represents a prime number.

您也许可以在维基百科上一个更好的描述，但是这是它的JIST。希望它可以帮助！

You can probably get a much better description on wikipedia, but this is the jist of it. Hope it helps!

这篇关于是否有人可以解释这是如何实现的作品？另外，可以把它变得更好？怎么样？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！