Оглавление > Наибольший простой делитель (F#)
05.02.2023

Наибольший простой делитель (F#)

Простые делители числа 13195 - это 5, 7, 13 и 29.
Каков самый большой делитель числа 600851475143, являющийся простым числом?

Решение:

Решим задачу при помощи рекурсивной функции с двумя параметрами: число num и делитель d

  • если число равно 0 то где-то ошибка
  • если число равно 1 то задача решена
  • если число не делится на текущий делитель то увеличиваем делитель на единицу и продолжаем
  • если делится - делим и продолжаем

делить начинаем с двух

let x = 600851475143L

let rec ans (num: int64) (d: int64) =
    match num with
    | 0L -> 0L //error
    | 1L -> d
    | _ when num % d <> 0 -> ans num (d + 1L)
    | _ -> ans (num / d) d

let answer = ans x 2L
printfn $"the answer is {answer}" //the answer is 6857