Have Geek Brain

Prime divisors of a number in ML

In ML, I want to get the prime divisors of a number. How can I do this, I start.

-1


a source to share


2 answers


Using a simple trial division, this starts with p=2

and re-divides n

by p

, increasing p

as it appears.



open LargeInt  (* if you want to work with huge numbers like 5000000000 *)
infix 7 quot rem
val prime_factors =
  let fun trial_division p n =
    if p > n then nil else
      if n rem p = 0
        then p :: trial_division  p      (n quot p)
        else      trial_division (p + 1)  n
  in trial_division 2 end
+2


a source


There are several general algorithms for finding prime divisors of an integer: see wikipedia . Trial division with a simple criterion of the simplest, simplest, simplest understanding.



Find or develop an algorithm in pseudocode; only then worry about how to put it in ML.

+1


a source






More articles:


All Articles