Factoring by trial division is an algorithm where a given integer is tested for divisibility by each prime in order until all its factors are discovered. It is the easiest algorithm to understand and the simplest to implement, but not always the most efficient.
Depending on the implementation, the algorithm can be provided with a list of primes. If, for example, the implementation is to be limited to 16-bit unsigned integers, it might make sense to provide a list of the primes up to 257. Otherwise, the list of primes could be gathered on the fly, or a performance penalty could be accepted by allowing certain “could-be primes”.
Call the trial division algorithm with an integer .
Test if is an integer. If it is, reset , set prime flag to false and test if will divide again. As many times as indicated, add to the list of factors, or add it once to the list of factors and increment the appropriate exponent accordingly. Increment once the length of the factor list.
Increment and see if . Also check that . If both of these conditions are true, repeat the previous step.
If prime flag is true, place in the first spot of the factor list and set factor list length to 1.
Return the factor list (and if applicable, the exponent list). It might or might not be a good idea to expose the prime flag to the calling function.
For example, . Clearly 2 doesn’t divide evenly, a human can tell on sight. Since it’s a small number, the digit sum test for 3 is applied quickly enough, and it returns false. We don’t need to try 5, though a computer does. Then, dividing by 7, we get the integer 4693, but 7 doesn’t divide again. Neither does 11. 4693 divided by 13 gives us 361. If this was a recursive implementation, it would recognize that 361 is 19 squared. Ergo, the factorization is .
To give another example: given , trial division would take 196 divisions. The second division would find 3 is a factor, the third would confirm 3’s exponent is 1, and it would take almost a couple hundred more divisions to get to 1187 and the certainty that 470347 must be a prime and the factors are hence 3 and 470347. Of course, with numbers of this size, a computer can perform hundreds of divisions in the blink of an eye.
Let’s try 522611488293. This number is almost “unfair” to an implementation lacking a list of primes provided beforehand, or even an implementation that remembers the primes it has tried. The second factor, 370373, ends a prime gap of 110 consecutive composites. It’s enough to slow down a computer implementation of trial division, even one that actually wastes time trying on such composites as 370263, 370267, 370269, etc. but not by much.
This last example, 4393547637856664251490043044051018234292171475232959, is an example of what not to even try to factor with trial division. Its square root is more than , and the logarithmic integral tells us there might be about primes to test divide in trying to factor this number.
0.1 External links
http://www.btinternet.com/ se16/js/factor.htmHenry Bottomley’s Prime Factors Calculator
http://www.geocities.com/primefan/Factorer.htmlPrimeFan’s Number Factorer
|Date of creation||2013-03-22 16:39:00|
|Last modified on||2013-03-22 16:39:00|
|Last modified by||CompositeFan (12809)|