StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>The problem with the idea of storing a list of primes p<=10^9 to factor numbers N<=10^18 is that for any particular N you would still need to loop over the primes p<=sqrt(N) and check whether or not N%p==0. This is not the fastest way to do business.</p> <p>It's not clear from your question if you want to factor a bunch of numbers that are order 10^18, or if you want to factor <strong>all</strong> numbers N<=10^18. The first case is doable depending on how many N you want to factor and how fast it needs to be. The second case, factoring <strong>all</strong> numbers N<=10^18, is not doable, because that would entail more than 10^18 operations (at least one for each number to be factored). Considering that computers can do on the order of 10^9 operations per second, and there are on the order of 10^7 seconds in the year, you'd be factoring for a long time.</p> <p>If you just want to factor a bunch of numbers N on the order of 10^18, then there are lots of ways to do this. The "best" way depends on the properties of the specific numbers. For example, random integers around 10^18 are a lot easier to factor on average than integers that are the product of two primes each of order 10^9, because small factors can be eliminated with trial division before moving to a more sophisticated algorithm. This is more a computational number theory question than a programming question. If this is your question, I recommend to it to the <a href="http://www.mersenneforum.org/forumdisplay.php?f=19" rel="nofollow">Factoring section of mersenneforum.org</a>. </p> <p>If you want a quick and dirty solution that is not ridiculously slow then don't reinvent the wheel. Try for example GMP-ECM or see if PARI/GP can solve your problem.</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