Может кто-нибудь объяснить, как работает эта реализация? Кроме того, это может быть сделано лучше? Как?

Question

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

Я не совсем понимаю, что происходит в этой программе, и надеялся, что кто-нибудь сможет мне это объяснить?Я прокомментировал конкретные строки, вызывающие у меня проблемы / то, что я понимаю, строки должны делать.Большое спасибо за помощь!:)

Answer 1

Ознакомьтесь с алгоритмом Сито Эратосфена .В Википедии даже есть анимированный GIF, демонстрирующий процесс.И ваш код - это просто прямая реализация.

Answer 2

Да, это ваша основная реализация Решета Эратосфена. Есть немало способов, которыми вы можете улучшить его, но давайте сначала рассмотрим основной принцип.

То, что вы делаете, - это создание массива логических значений. Индекс в массиве представляет число, которое мы тестируем, чтобы увидеть, является ли оно простым или нет.

Теперь вы начнете проверять каждое число, чтобы узнать, простое ли оно. Во-первых, определение простого числа: «все числа делятся ТОЛЬКО на себя и 1 без дробного числа».

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

Вы начинаете с INDEX 2 (число 3), потому что в зависимости от вашего определения 1 и 2 всегда просты. (Некоторые определения говорят, что 1 не простое число).

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

Если число ранее было помечено как не простое, мы не беспокоимся о текущей итерации.

numberOfPrimes++;

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

Если ИНДЕКС, в котором мы находимся в настоящее время, не был помечен как простое число, оно должно быть одним, поэтому мы увеличиваем число найденных простых чисел. Следующий фрагмент кода, который я предполагаю, является частью требований программы, которая гласит, что, если найдено 10001 простых чисел, программа должна завершиться. Эта часть может быть опущена, если вы действительно хотите проверить простые числа до максимального числа, определенного вместо определенного числа простых чисел.

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

Именно здесь начинается настоящая магия сита. Из определения простого числа число не может быть простым, если оно делится на что-либо, кроме себя и 1. Поэтому для любого нового числа, которое мы находим, что это простое число, мы можем пометить все его факторы как НЕ простые. Например, первую итерацию цикла for мы начинаем с 3. Поскольку sieve [2] имеет значение false (ранее не посещали), оно является простым (AND 3 IS PRIME!). Тогда все остальные 3 не могут быть простыми числами. Упомянутый выше цикл for проходит через все сито и помечает все факторы 3 как ложные Так что цикл будет делать: sieve [5] = true; сито [8] = правда ... до конца сита.

Теперь, когда вы достигнете первого числа, большего, чем максимум, определенный изначально, вы можете быть уверены, что любое число, имеющее множитель, было помечено как не простое число. В результате получается логический массив, где каждый индекс, помеченный как ложный, представляет собой простое число.

Вероятно, вы можете получить намного лучшее описание в Википедии, но это суть. Надеюсь, это поможет!

Answer 3

Я считаю, что самый простой способ понять что-то - это разобрать его. Поэтому давайте пройдемся по циклу несколько раз, ладно?

Рассвет первой итерации

& минус; 9999998 Значения остаются & минус;

i = 2
sieve[2] равно false, поэтому мы продолжаем текущую итерацию.
numberOfPrimes = 1 и, таким образом, мы продолжаем обработку
Установите каждое кратное от 2 до true в sieve[].

Рассвет второй итерации

& минус; 9999997 Значения остаются & минус;

i = 3
sieve[3] равно false, поэтому мы продолжаем текущую итерацию.
numberOfPrimes = 2 и таким образом мы продолжаем обработку
Установите каждое кратное от 3 до true в sieve[].

Рассвет третьей итерации

& минус; 9999996 Значения остаются & минус;

i = 4
sieve[4] равно true (с первой итерации). Перейти к следующей итерации.

и т.д ... но в этом случае луна не врезается в Термина .

Answer 4

for ( int j = i+i; j < maxLimit; j += i ) //dont understand the point of this loop logically
                sieve[j] = true;          //testing if the value in the array is true again ?

Это не тестирование, а настройка.Этот цикл устанавливает все элементы в массиве с индексами, кратными от i до true.Если i равно 2, то элементы 4, 6, 8 ... будут установлены на true.Когда i равно 3, элементы 6, 9, 12 ... будут установлены на true и т. Д.

И, как вы можете вывести по первым if,

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

... все элементы true соответствуют непростым числам.

Answer 5

Это алгоритм для поиска простых чисел между 1 и заданным максимальным пределом.

И цикл, добавленный 2-ой, должен выполнить для числа, которое делится на любое другое число . так что для первого внешнего цикла все числа, делимые на два, будут установлены в true, затем делятся на 3, затем на 4 и т. д. и числа, для которых логический массив содержит false, являются простыми числами .

Answer 6

Цикл, о котором идет речь, - это не проверка на истинные значения, это установка истинных значений.

Он проходит через все кратные простого числа и помечает его как не простое до maxLimit. Вы заметите, что в коде нет другой математики для определения того, что является основным, а что нет.