FunTrivia Homepage New Questions Unanswered Post a Question Goto Qn # Archives

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

Question #93092. Asked by gentlegiant17. (Mar 03 08 9:50 AM)

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

 The number of prime numbers is infinite. But, is the number of decades where all odd numbers are prime, except for the one ending in 5 of course, also infinite (e.g. 11, 13, 17, 19 and 101, 103, 107, 109)?

Suggested Related FunTrivia Quizzes - 90,000 currently online

1 "The Number 23" (2007)
 If you saw this film directed by Joel Schumacher and starring Jim Carrey, I hope you enjoy this quiz.
N Easy
10 Q
christopherm
Aug 19 07
1173 plays
2 The Number 2s of the 1960s
 These songs (please excuse the cliche) were the bridesmaids, but not the bride. I hope you have fun with this one.
1960s Music Tough
10 Q
Jun 20 07
1065 plays
3 Number 1s of the '90s
 I will give you the first line of a song that was number 1 in the '90s and you have to give me the name of the song. All of these songs were number one in the UK singles chart.
1990s Music Average
25 Q
raggedyann
Aug 30 04
5820 plays

"Ask FunTrivia" is for entertainment purposes only, and answers offered are unverified and unchecked by FunTrivia. We cannot guarantee the accuracy or veracity of ANY statement posted. Feel free to post an updated response if you feel that an answer is inadequate or incorrect. Please thoroughly research items where accuracy is important to you using multiple reliable sources. By accessing our website, you agree to be bound by our terms of service.