What is the best known algorithm for prime factorization of a given number?

wahoowa94

It is difficult to say which algorithm is the best known as there are many complex algorithms, not all of which are reliable. However, probably the simplest method of finding factors is so-called "direct search factorization" (a.k.a. trial division). In this method, all possible factors are systematically tested using trial division to see if they actually divide the given number. It is practical only for very small numbers. http://en.wikipedia.org/wiki/Trial_division Mar 03 08, 10:35 AM

rxbigdawg

For larger numbers it seems there is no good method known so far. I read on one link that it took 50 computer years to compute the factors of a 200 digit number! Maybe a math genius will devise an algorithm some day. Mar 03 08, 10:59 AM

queproblema

GG17 asks for the "best known," not the most elegant, and does not specify large numbers. Since many more people master 8th grade math than college math, more people would know the simplest way, which would be the good old "factor tree"--kids love 'em! This one is super simple, more like 5th grade; the highest number is 100. http://www.mathgoodies.com/factors/prime_factors.html If you don't want to wait for the animation to load or don't care to play a kiddie game, this, without naming it, shows a factor tree after first showing simple division by prime numbers. http://amby.com/educate/math/2-1_fact.html On somewhat larger numbers, up to 10 digits or so, either method is practical and easy with the aid of a table of prime numbers and knowledge of the divisibility rules. http://mathforum.org/dr.math/faq/faq.divisibility.html http://www.factmonster.com/ipka/A0876084.html Mar 03 08, 7:35 PM