CODEWITHSUNDEEP
sml
user4348719
user4348719

Reputation: 351

Factoring a large number

Need a way of factoring a large number in ml, disregarding 1 and the number. My way only works for small numbers, it involves basically starting at the lowest possible 2 factors and checking if when multiplied they equal the number, otherwise keep looping. This does not work for large numbers since it would take too many recursive calls

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;

Upvotes: 0

Views: 410

Answers (1)

Matt
Matt

Reputation: 4049

The typical way of factoring a number n is to loop from 2 to sqrt(n), each time checking if n is divisible by your current loop index. There are a couple of problems with your implementation. First, (as mentioned in one of the above comments) if the number given is prime, you will go off into an infinite loop. Second, you are checking redundant cases. A function to get all factors of a number is given below:

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

This seems to be able to handle large numbers, and has the added benefit of giving all factors of a number. if you want it to short circuit after finding one solution, then you can change lp(i+1, (i, n div i)::factors) to (i, n div i) and remove the second parameter from lp

Upvotes: 1

Related Questions