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