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)
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. |
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.