StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>Actually there are several more efficient ways to find factors of big numbers (for smaller ones trial division works reasonably well). </p> <p>One method which is very fast if the input number has two factors very close to its square root is known as <a href="http://en.wikipedia.org/wiki/Fermat's_factorization_method" rel="noreferrer">Fermat factorisation</a>. It makes use of the identity N = (a + b)(a - b) = a^2 - b^2 and is easy to understand and implement. Unfortunately it's not very fast in general.</p> <p>The best known method for factoring numbers up to 100 digits long is the <a href="http://en.wikipedia.org/wiki/Quadratic_sieve" rel="noreferrer">Quadratic sieve</a>. As a bonus, part of the algorithm is easily done with parallel processing.</p> <p>Yet another algorithm I've heard of is <a href="http://en.wikipedia.org/wiki/Pollard's_rho_algorithm" rel="noreferrer">Pollard's Rho algorithm</a>. It's not as efficient as the Quadratic Sieve in general but seems to be easier to implement.</p> <hr> <p>Once you've decided on how to split a number into two factors, here is the fastest algorithm I can think of to find the largest prime factor of a number:</p> <p>Create a priority queue which initially stores the number itself. Each iteration, you remove the highest number from the queue, and attempt to split it into two factors (not allowing 1 to be one of those factors, of course). If this step fails, the number is prime and you have your answer! Otherwise you add the two factors into the queue and repeat.</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload