Оглавление > Сложение простых чисел (F#)
15.02.2023

Сложение простых чисел (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