Integer factorization. Trial division

Integer factorization using trial division algorithm.

This page exists due to the efforts of the following people:



Created: 2014-07-18 14:22:09, Last updated: 2021-03-06 08:57:43
Creative Commons Attribution/Share-Alike License 3.0 (Unported)

This content is licensed under Creative Commons Attribution/Share-Alike License 3.0 (Unported). That means you may freely redistribute or modify this content under the same license conditions and must attribute the original author by placing a hyperlink from your site to this work Also, please do not modify any references to the original work (if any) contained in this content.

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

PLANETCALC, Integer factorization. Trial division

Integer factorization. Trial division

The file is very large. Browser slowdown may occur during loading and creation.

Integer factorization

In number theory, integer factorization or prime factorization is the decomposition of a composite number into smaller non-trivial divisors, which when multiplied together equal the original integer.

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

Given an integer n (the integer to be factored), the 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.

With this ordering, there is no point in testing for divisibility by four if the number has already been determined not divisible by two, and so on for three and any multiple of three, etc.

Therefore, you can reduce the effort by selecting only prime numbers as candidate factors. Furthermore, the trial factors need to 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 the wiki link above.


URL copied to clipboard
PLANETCALC, Integer factorization. Trial division