Просто о простых числах…

в 18:03, , рубрики: Алгоритмы, математика

Эратосфен, видимо, не был программистом и в алгоритмах разбираться не спешил. Злоупотребляя использованием решета, которое он описал, вы недооцениваете своё время…

Кто-нибудь всерьёз задумывался что минимально необходимо для вычисления последовательности простых чисел от первого до 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.: Несмотря на медленность операций, решетом Эратосфена вычисляют диапазоны простых чисел или просто проверяют отдельные числа на простоту. Но когда нужна их полная последовательность, то думать необходимо в примерно таком ключе как описано выше.
Но решето все равно перебирает все числа, пытаясь делить на них тестируемое число. Единственное его “достоинство” — оно не тратит память на хранение промежуточных вычислений. Но, возможно, времени тратится на проверку одного числа больше, чем нахождение всех предыдущих простых чисел по данному алгоритму.

Автор: Барак Адама

Источник

* - обязательные к заполнению поля


https://ajax.googleapis.com/ajax/libs/jquery/3.4.1/jquery.min.js