Сито реализации Эратосфена не проверяет определенные числа


Я пишу программу для поиска простых чисел, используя хорошее старое сито алгоритма Эратосфена (хотя и с изюминкой). Для того, чтобы вдвое уменьшить размер необходимого массива байтов, я не представляю никаких четных чисел, а придерживаюсь нечетных (вычисляя их положение в массиве целочисленным делением на два).

Однако у меня есть одна проблема. Моя программа, кажется, не распознает 17 или 113 как простые числа, хотя они действительно простые числа. Вот мой код:

public class Eratosthes {

    byte[] checklist;
    int range;

    public EratosthesConcurrent(int range) {
        this.range = range/2;
        this.checklist = new byte[this.range];
        this.initAllChecked();
        this.findPrimesSeq();
        this.printPrimes();
    }

    private void initAllChecked(){
        for(int i = 1; i < checklist.length; i++){
            checklist[i] = 1;
        }
    }

    private void crossOut(int i){
        checklist[i/2] = 0;
    }

    private void findPrimesSeq(){
        int curr = 3;
        outer: while(curr < range*2){
            for(int i = curr*curr; i < range*2; i+=2*curr){
                if(i != curr && i%curr == 0){
                    if(i == 113){
                        System.out.println(curr);
                    }
                    crossOut(i);
                }
            }

            secondLoop: for(int i = curr; i < range*2; i++){
                if(checklist[i/2] == 1 && curr != i){
                    curr = i;
                    break secondLoop;
                } else if(i == range*2-1 || i == range*2-2){ //Should be changed, might miss the last prime
                    break outer;
                }
            }
        }
    }

    public void printPrimes(){
        for(int i = 1; i < range; i++){
            if(checklist[i] == 1){
                System.out.println("Prime found: " + ((i*2)+1));
            }
        }
    }
}

Добавление следующий способ изменения не производить никаких выходных данных:

if(i == 17 || i == 113){
    System.out.println("Found one of the numbers");
}

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

Я был бы очень рад, если бы кто-нибудь нашел ошибку в моей программе-я сам отлаживал ее часами, безрезультатно. Заранее спасибо.
2 3

2 ответа:

Проблема, похоже, в том, что вы не проверяете деление на 2.

Вы вызываете crossOut(16) в какой-то момент (в частности, как кратное 4), что вычеркивает соответствующее значение для 17. Аналогично для 112, вызывающего вычеркивание 113.

Изменение:

if (i != curr && i % curr == 0) {

Кому:

if (i % 2 != 0 && i != curr && i % curr == 0) {

И оба они печатаются как простые числа.

Кроме того, я немного обеспокоен тем, что именно делает этот цикл - я не смотрел на выход слишком много подробно, хотя на самом деле это все простые числа, но я думаю, что вы должны зацикливаться на множествах curr, первый из которых 2*curr (не curr*curr), приращение между ними curr (не 2*curr), хотя я не говорю, что вы сделали неправильно, так как мне нужно немного больше времени, чтобы понять, как именно ваш код решает эту проблему.

for(int i = curr*curr; i < range*2; i+=2*curr){

Первое значение = 9, затем переходит в 15

Карр = 3 - 3*3 = 9

I += 2 * curr = 9 + 6

Псевдо:

outerNum = sqrt[range]
array[boolean] size of range
array[0 & 1] = false

for i = 2 to outernum
       for j  = i to range
           if j % i != 0
               array[j] = false

for i = array[boolean] length
     print if array[i] = true

Это из памяти, так что простите, если какие-то ошибки.