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