Сита Эратосфена считает, что все числа просты после 127

Question

У меня проблемы с моим ситом Эратосфена. Я хотел написать сито, которое не требовало бы массива всех чисел вплоть до наибольшего простого числа, которое вы хотите, а просто отслеживало каждое простое число, кратное достижению сита. Это означает, что вам не нужно выполнять всю работу заранее, а просто определить следующий штрих, когда вам это нужно. Также было бы легко добавить функции интерфейса, такие как «найти K простых чисел, начинающихся с N». Вот псевдокод:

Begin with current number set to 2
Loop:
    If prime queue is not empty:
        Peek at the top prime in the queue
        If current > top, we can move top to the next multiple
            Remove the top prime from the prime queue
            Increment top to its next multiple
            Re-add it to the queue
        If current == top, current is not a prime
            Increment current number to next integer
        If current < top, we've found a prime
            Break
Push current number onto prime queue
Increment current number to next integer
Return the new prime

Так вот в чем проблема: я правильно вычисляю первые 31 простых чисел (до 127), но после этого он думает, что каждое число является простым. Я поместил свой код на Ideone - я надеюсь, что это поведение некоторых коллекций Java или тривиальная ошибка, а не сам алгоритм. Я не могу придумать причину, по которой алгоритм должен сломаться после определенного числа простых чисел. Я подтвердил вручную, что после 127, если куча правильно упорядочена, мой алгоритм должен распознавать 128 как не простое число, но это не то, что код показывает мне.

Есть предложения?

http://ideone.com/E07Te

(Конечно, я увеличу на 2 (чтобы пропустить все не простые числа) после того, как заработаю базовый алгоритм. Возможно, я также сделаю Sieve итеративным.)

Answer 1

Ваша проблема

top.multiple == current

в связи с

Integer current = 2;
Integer multiple;

Имеется кэш Integer с небольшим абсолютным значением, от -128 до 127, если я правильно помню, поэтому сравнение с использованием == сравнивает идентичные экземпляры для значений, меньших 128. Но с 128 по вы получаете новый штучный Integer для current, и это объект, отличный от того, на который ссылается top.multiple.

Сравните, используя equals или объявите int current;, чтобы решить.

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

Answer 2

Вы не проверяете весь свой список:

Куча сита после 31: [[127: 127], [11: 132], [2: 128]

Вы попадаете в132, что> 128, и, таким образом, нажмите break;, прежде чем проверять на 2 * 64.