FactorizerApplet

Enter a number in the text box, and hit Go! to get that number's prime factorization. Please keep your number under 2,147,483,647 (the limit for 32-bit integers) and refrain from using any arithmetic operators such as '(', ')', '+', '*', etc.

Source code for FactorizerApplet (html version)

Further Questions

1. Any factor returned that is less than 24,990,001 is guaranteed to be prime.
a) Why is this true?
b) Furthermore, no guarantees can be made about results above this threshold. Why?
Hint: Consider the factorization algorithm. What is its inherent limit? Be bold, examine the source code!
c) Sketch how to fix this applet so that it can guarantee prime results up to 25,000,000.
d) Implement the change.

2. Despite the above limitation, the implemented algorithm is very fast for small 'n'. However, it will not factor some larger numbers.
a) Suggest a new algorithm which is not limited by the size of 'n'. Implement it in pseudocode.
b) Learn how the pros do it! Research "Elliptic Curve Method" and "Quadratic Sieve" on Google. These techniques easily factor numbers upwards of 20 and 30 digits.



Created by Andrew Freed, arf132@psu.edu on January 30, 2002.
Modified by Andrew Freed, arf132@psu.edu on April 15, 2002.

Development of this applet was sponsored by the Penn State Fund for Excellence in Learning and Teaching (FELT), project "Java-based Teaching of Mathematics in Information Sciences and Technology", supervised by Frank Ritter and David Mudgett.