Для достаточно малых чисел x% n до sqrt (x) ужасно быстро и легко кодируется.
Простые улучшения:
только тест 2 и нечетные числа.
тест 2, 3 и кратные 6 + или - 1 (все простые числа, кроме 2 или 3, кратны 6 +/- 1, поэтому вы по сути просто пропускаете все четные числа и все числа, кратные 3
тестировать только простые числа (требуется вычислить или сохранить все простые числа до sqrt (x))
Вы можете использовать метод sieve для быстрого создания списка всех простых чисел до некоторого произвольного предела, но он, как правило, требует больших затрат памяти. Вы можете использовать прием, кратный 6, чтобы уменьшить использование памяти до 1/3 бита на число.
Я написал простой простой класс (C #), который использует два битовых поля для кратных 6 + 1 и кратных 6-1, а затем выполняет простой поиск ... и если число, которое я тестирую, находится за пределами сита, затем он возвращается к тестированию на 2, 3 и кратные 6 +/- 1. Я обнаружил, что создание большого сита на самом деле занимает больше времени, чем вычисление простых чисел на лету для большинства задач Эйлера, которые я решил до сих пор. Принцип KISS снова поражает!
Я написал простой класс, который использует сито для предварительного вычисления меньших простых чисел, а затем полагается на тестирование на 2, 3 и кратные шести +/- 1 для тех, которые находятся за пределами диапазона сита.
person
user17184
schedule
01.12.2008