Integer factorization. Trial division

Integer factorization using trial division algorithm.

All of sudden, I have to factorize some integers. Since I did not suppose my integers to be very big numbers, I've implemented trial division method. Method description is below the calculator.

PLANETCALC, Integer factorization. Trial division

Integer factorization. Trial division


Integer factorization


And, since trial division is the easiest to understand of the integer factorization algorithms, here are couple of sentences from wikipedia:

Given an integer n (the integer to be factored), trial division consists of systematically testing whether n is divisible by any smaller number. Clearly, it is only worthwhile to test candidate factors less than n, and in order from two upwards because an arbitrary n is more likely to be divisible by two than by three, and so on.


Therefore, effort can be reduced by selecting only prime numbers as candidate factors. Furthermore, the trial factors need go no further than \sqrt{n} because, if n is divisible by some number p, then n = p × q and if q were smaller than p, n would have earlier been detected as being divisible by q or a prime factor of q.

Trial division is a laborious algorithm, yet it is good for small numbers. More can be found at wiki link above.


Creative Commons Attribution/Share-Alike License 3.0 (Unported) PLANETCALC, Integer factorization. Trial division