Задача
Сумма простых чисел меньше 10 равна 2 + 3 + 5 + 7 = 17.
Найдите сумму всех простых чисел меньше двух миллионов.
Решение
Надо сказать, что решение здесь уже заведомо известно, так как в предыдущих задачах это уже встречалось.
Обжёгшись ранее на оптимизациях, для начала попробую лобовое решение:
Как мы должны помнить, здесь для поиска простого числа перебираются все множители числа n, но оптимизация заключается в том, чтобы перебирать их только до sqrt(n).
Также ради разнообразия я использовал код:
sum += n & is_prime(n);
Вместо проверки с помощью if. Как это работает, думаю понятно.
Ссылка на онлайн-компилятор с текстом программы
Второй вариант это использовать решето Эратосфена, но оно потребует массив в 2 миллиона элементов. Хотя это и не смертельно, в прошлый раз я пообещал сделать вариант, который будет использовать фиксированный массив небольшой длины для любого множества чисел.
Поэтому представляю вашему вниманию...
Решето Всратосфена
Общая концепция: мы используем массив неограниченной длины, но виртуальный. Позиция в виртуальном массиве это sieve_pos, она показывает, до какого места мы действительно дошли. Всегда доступен только один рабочий сегмент виртуального массива, размером SIZE. Виртуальный массив увеличивается порциями SIZE, и его текущая длина хранится в переменной limit. А внутри сегмента локальная позиция хранится в переменной local_pos, которая является остатком от sieve_pos / SIZE.
Рабочий сегмент заполняется как обычно по алгоритму решета Эратосфена. Когда мы находим очередное простое число, то начиная от квадрата этого числа (если квадрат числа всё ещё находится в текущем сегменте) и до конца сегмента помечаем кратные числа как непростые. При этом важно то, что все найденные простые числа надо сохранять в списке.
Это происходит здесь:
Когда sieve_pos достигает конца текущего виртуального массива, limit увеличивается на SIZE, и рабочий сегмент инициализируется заново. Для этого мы стираем всё, что там есть, затем проходим по списку ранее сохранённых простых чисел (для этого и нужно их хранить) и с помощью каждого из них дозаполняем сегмент, как будто бы заполнение продолжается непрерывно после предыдущего сегмента.
Это проиcходит здесь:
Самым большим затыком было определить, с какой позиции в сегменте нужно продолжать заполнение.
Например, рассмотрим простое число 3 и размер сегмента 32.
Сегмент заполняется кратными 3 числами до 30. Следующее значение должно быть 33, но оно попадает уже в следующий сегмент.
Когда мы открываем следующий сегмент, то достаём из списка число 3 и продолжаем заполнение. Но с какой позиции его начать? Если в прошлом сегменте мы закончили на позиции 30, то в этом сегменте надо начать с позиции 1 (у числа 3 одна позиция осталась в предыдущем сегменте и две в этом, позиции считаются с 0 до SIZE-1).
Всё это, как мне казалось, должно выполняться одним математическим действием, но почему-то в этом месте я очень сильно туплю. Поэтому сделал топорно.
Сколько позиций осталось в предыдущем сегменте (это остаток от деления предыдущего limit на число):
pos = (limit - SIZE) % prime
Этот остаток всегда меньше числа, поэтому в новом сегменте стартовая позиция будет:
pos = prime - pos
И вроде бы всё хорошо. Например, для числа 3, SIZE = 32, limit = 64:
pos = (64 - 32) % 3 = 2
pos = 3 - pos = 1
Но если взять число 2, то получим неверный ответ:
pos = (64 - 32) % 2 = 0
pos = 2 - pos = 2
Cуть в том, что если остаток 0, то с 0 и надо начинать. Поэтому мне пришлось добавить дополнительную проверку:
Я так и не понял, что тут можно упростить – голова просто моментально отключается. Ну в общем, оно работает в таком виде.
Ссылка на онлайн-компилятор с текстом программы
Производительность
Замеры я делал на локальной машине, потому что в онлайн-компиляторе всё крайне нестабильно.
Итак, полунаивный метод отрабатывает за примерно 1.3 секунды.
Примерно такое же время требуется решету Всратосфена – 1.2 секунды.
Но это при размере рабочего сегмента в 256 чисел, что, согласитесь, совсем немного. Если увеличивать размер сегмента, то время сразу начинает укорачиваться. Например, если сделать размер 16 килобайт (что тоже совсем немного), то программа отработает всего за 40 миллисекунд, то есть в 32 раза быстрее.
При дальнейшем увеличении размера скорость уже почти не увеличивается.
Оставшаяся проблема это хранение найденных простых чисел. Для них требуется массив в 150 тысяч 64-битных элементов, или 1.2 мегабайта памяти.
Это тоже не смертельно, но есть возможность одного улучшения. Разница между соседними простыми числами весьма мала, поэтому в списке простых чисел можно хранить не сами числа, а разницу между ними. Это позволит сократить размер одного элемента до 8 бит. Сам список нужен только для того, чтобы дозаполнять сегменты, и так как цикл начинается с первого элемента списка, то следующие элементы легко восстанавливаются через суммирование.
Это я уже делать не буду, так как незачем :)
Вся подборка задач: