На моем компьютере вычисление первых 1 000 000 000 чисел занимает 4,8 секунды. Это даже быстрее, чем чтение из файла! 1021 *.
Проблема, однако, в том, что для этого требуется много памяти. Мое приложение Java просто дает сбой, когда я просто объявляю логический массив 1000000000.
Итак, я сделал две оптимизации памяти, чтобы заставить его работать
- Поскольку все простые числа после 2 равны нечетные числа, я вдвое меньше размера массива, отображая индексы на
int p = i * 2 - 1; - Затем вместо использования массива логических значений я использовал
BitSet, который работает с битовой операцией над массивом long.
С этими двумя оптимизациями использование решета Эратосфена позволяет вам вычислить btSet за 4,8 секунды. Насчет распечатки - это отдельная история;)