Сложение простых чисел (F#)

Сумма простых чисел меньше 10 равна 2 + 3 + 5 + 7 = 17. Найдите сумму всех простых чисел меньше двух миллионов.

Решение

• Воспользуемся решением из задачи про 10001-е простое число
• только изменим условие выхода из рекурсивной функции
• работает слишком медленно, поэтому вместо 2 млн поставим ограничение 200 тыс

let undiv lst a =
    lst |> List.forall (fun x -> a % x <> 0)

let rec check acc curr =
    if curr >= 200_000 then acc
    else if undiv acc curr then check (curr :: acc) (curr + 2)
    else check acc (curr + 2)

let time1 = System.DateTime.Now

let answer = check [ 2 ] 3 |> List.sumBy int64

let time2 = System.DateTime.Now

let dt = (time2 - time1).TotalMilliseconds

printfn $"the answer is {answer}, time = {dt:f0} ms" //the answer is 1709600813, time = 4799 ms

• почти 5 секунд до результата, это много, учитывая что задача все еще не решена

Оптимизация

• т.к. наивным методом решить не удалось, используем классический подход в виде решета Эратосфена (opens new window)
• для начала объявим функцию вычисления прошедшего времени в миллисекундах (timeFrom)
• запомним текущее время (t0)
• объявим функцию прибавляющую 2 к числу (plus2)
• заполним массив значениями от 2 до 199_999 (nums)
• в целях реализации алгоритма создадим цикл от начала до середины массива
  • если текущее значение не равно нулю тогда обнулим все числа, кратные текущему
  • таким образом в массиве nums остались только простые числа, а на месте составных - нули
• вычислим сумму и выведем результат

let timeFrom (t: System.DateTime) = (System.DateTime.Now - t).TotalMilliseconds

let t0 = System.DateTime.Now
let plus2 x = x + 2
let nums = Array.init (200_000-3) (plus2)
for i in [0..nums.Length/2] do
  if nums[i] <> 0 then
    for j in [i+nums[i]..nums[i]..nums.Length-1] do nums[j] <-0
let answer2 = Array.sumBy int64 nums
printfn $"the answer2 is {answer2}, time = {timeFrom t0:f0} ms" //the answer2 is 1709600813, time = 51 ms

• как видно подсчет суммы простых чисел менее 200 000 занял 51 миллисекунду
• меняем верхнюю границу на 2 млн, как и требуется в условии

let nums = Array.init (2_000_000-3) (plus2)

• и получаем ответ за 523 мс

printfn $"the answer2 is {answer2}, time = {timeFrom t0:f0} ms" //the answer2 is 142913828922, time = 523 ms