Просто о простых числах (быстрый инкрементный метод вычисления простых чисел)

Когда-то всерьёз задумался что минимально необходимо для вычисления последовательности простых чисел от первого до N? Берем всё необходимое и отбрасываем лишнее — рецепт успешной стратегии. В данном случае необходимо взять на вооружение все быстрые операции и отбросить все трудоемкие, вроде деления. А тот, кто решил описать простые числа через операции деления, похоже, сыграл злую шутку с человечеством. Шли тысячелетия, а а люди так и продолжают делить…

Сначала код:

public HashMap<Long, Long> serialPrimes() {    long range = Long.parseLong(this.range.getText().toString());    HashMap<Long, Long> primes = new HashMap<>(); //простые числа и их топпинги    HashMap<Long, ArrayList<Long>> spectres = new HashMap<>(); // непростые числа и их множители    HashMap<Long, ArrayList<Long>> toppings = new HashMap<>(); // топпинги и накопленные по ним спектры    for(long i = 2; i < range; i++){        if(toppings.keySet().contains(i)) { // если в таблице топпингов имеется ключ, равный текущему значению счетчика i            //переносим собранный спектр            ArrayList<Long> spectre = toppings.get(i);            spectres.put(i, spectre);            toppings.remove(i);            for(long spectreValue : spectre) {                // обновляем топпинг на один шаг дальше                long topping = primes.get(spectreValue) + spectreValue;                primes.put(spectreValue, topping);                // пополняем спектр новым значением                if(toppings.keySet().contains(topping)) {                    toppings.get(topping).add(spectreValue);                } else {                    ArrayList<Long> newSpectre = new ArrayList<>();                    newSpectre.add(spectreValue);                    toppings.put(topping, newSpectre);                }            }        } else { // если в таблице топпингов отсутствует ключ, равный текущему значению счетчика i            // записываем простое число            primes.put(i, i + i); // значение топпинга всегда больше текущего значения счетчика, ближайшее к нему    // делимое на ключ            // добавляем новое значение в топпинги            ArrayList<Long> newSpectre = new ArrayList<>();            newSpectre.add(i);            toppings.put(i + i, newSpectre);        }    }    return primes; }

Теперь пояснение.

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

Алгоритм можно перестроить для облачного API или P2P сети.

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

В алгоритме используются 3 таблицы:

• для простых чисел
• для непростых чисел и их множителей
• для относительной индексации значений в таблице простых чисел

Суть алгоритма следующая:

• Перебираем последовательно числа, начиная с 2 (цикл)
• Ищем значение счетчика в таблице T
• Если не находим, то это число простое
• сохраняем значение в таблицу простых чисел начальное значение топпинга равно 2*n (например, первое число цикла запишется как 2[4])
• в таблицу топпингов заносим взаимно обратное значение 4[2]
• переходим к следующей итерации
• Если же находим, то переносим собранный под этим ключом спектр в таблицу спектров непростых чисел
• После этого для каждого значения этого спектра увеличиваем значение топпинга в таблице простых чисел на величину этого простого числа (получается небольшой вложенный цикл, который теоретически можно параллелить)
• увеличиваем топпинг
• добавляем взаимно обратное значение в топпинги
• переходим к следующей итерации

Сохранив таблицы и запомнив верхнюю границу пройденного диапазона можно продолжить вычисление с того же места, где в прошлый раз закончили.

На моем телефоне я вычислял в диапазоне чисел до 1.500.000. Менее, чем за 2 минуты. На эмуляторе получалось по-разному, считал до 3.000.000. Считало 96 секунд первый раз, и ускорилось до 14 секунд (при повторном пересчете, видимо связано с процессом выделения памяти приложению).

В диапазоне от 2 до 3.000.000 лежит 216.816 простых чисел.

Android-пример

P.S.: Несмотря на медленность операций, решетом Эратосфена вычисляют диапазоны простых чисел или просто проверяют отдельные числа на простоту. Но когда нужна их полная последовательность, то думать необходимо в примерно таком ключе как описано выше.
Но решето все равно перебирает все числа, пытаясь делить на них тестируемое число. Единственное его “достоинство” — оно не тратит память на хранение промежуточных вычислений. Но, возможно, времени тратится на проверку одного числа больше, чем нахождение всех предыдущих простых чисел по данному алгоритму.