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 раза, что является неплохим результатом для столь малых изменений.