Факторинг большого количества

Question

Нужен способ факторинга большого количества в мл, без учета 1 и числа. Мой способ работает только для небольших чисел, он включает в себя в основном запуск с минимально возможными 2 факторами и проверку, если при умножении они равны числу, в противном случае продолжайте цикл. Это не работает для больших чисел, так как это заняло бы слишком много рекурсивных вызовов

fun factor n= 

let 
    val f1 = 2 
    val f2 = 3 
    fun lp f1 f2 = if f1 *f2 = n then (f1,f2) 
           else if f2 = (n-1) 
           then lp (f1+1) 2 
           else lp f1 (f2+1) 
in 
    (lp f1 f2) 
end; 

Answer 1

Типичный способ факторинга ряд n является цикл от 2 до sqrt(n), каждый раз проверяя, если n делится на ваш текущий индекс цикла , Есть несколько проблем с вашей реализацией. Во-первых, (как упоминалось в одном из приведенных выше комментариев), если указанное число является простым, вы перейдете в бесконечный цикл. Во-вторых, вы проверяете избыточные случаи. Функция для получения всех факторов ряда приводится ниже:

fun factor n = 
    let val sqrtN = Real.ceil(Math.sqrt (Real.fromInt n)) 
    fun lp(i, factors) = 
      if i > sqrtN 
      then factors 
      else 
       if Int.mod(n, i) = 0 
       then lp(i+1, (i, n div i)::factors) 
       else lp(i+1, factors) 
    in lp(2, nil) end 

Это, кажется, чтобы быть в состоянии обрабатывать большое количество, и имеет дополнительное преимущество, давая все факторы ряда. если вы хотите, чтобы он закорочился после нахождения одного решения, вы можете изменить lp(i+1, (i, n div i)::factors) на (i, n div i) и удалить второй параметр из lp