Оглавление > 10001-е простое число
10.02.2023

10001-е простое число

Выписав первые шесть простых чисел, получим 2, 3, 5, 7, 11 и 13. Очевидно, что 6-е простое число - 13. Какое число является 10001-м простым числом?

Решение

  • undiv это функция проверки не делится ли число (a) на любое число из списка (lst)
let undiv lst a = lst |> List.forall (fun x -> a%x <> 0)
  • check это основная рабочая рекурсивная функция
    • если дошли до 10001 элемента тогда возвращаем список, иначе:
    • если текущее число не делится на все предыдущие, то добавляем его в начало списка и переходим к проверке следующего, иначе:
    • число не простое, проверяем следующее
let rec check acc curr = 
  if List.length acc >= 10001 then acc else
  if undiv acc curr then check (curr::acc) (curr+1)
  else check acc (curr+1)
  • в этой задаче большой объем вычислений, поэтому решено измерить время выполнения
    • запомнили текущее время
    • вычислили ответ
    • снова запомнили время
    • вычислили разницу
    • вывели ответ и время в мс
let time1 = System.DateTime.Now
let answer = check [] 2 |> List.head
let time2 = System.DateTime.Now
let dt = (time2-time1).TotalMilliseconds
printfn $"the answer is {answer}, time = {dt:f0} ms" //the answer is 104743, time = 6031 ms

Оптимизация

  • 6 секунд это довольно много, хотя и приемлемо, но применим очевидную оптимизацию: все простые числа (кроме 2) - нечетные, поэтому можем начать с 3 и добавлять по 2
  • Новый листинг и новые результаты:
let undiv lst a = lst |> List.forall (fun x -> a%x <> 0)
let rec check acc curr = 
  if List.length acc >= 10001 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.head
let time2 = System.DateTime.Now
let dt = (time2-time1).TotalMilliseconds
printfn $"the answer is {answer}, time = {dt:f0} ms" //the answer is 104743, time = 2651 ms
  • как видно время выполнения уменьшилось более чем в 2 раза, что является неплохим результатом для столь малых изменений.