StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>There is no need to calculate <code>smallprimes</code> using <code>primesbelow</code>, use <code>smallprimeset</code> for that.</p> <p><code>smallprimes = (2,) + tuple(n for n in xrange(3,1000,2) if n in smallprimeset)</code></p> <p>Divide your <code>primefactors</code> into two functions for handling <code>smallprimes</code> and other for <code>pollard_brent</code>, this can save a couple of iterations as all the powers of smallprimes will be divided from n.</p> <pre><code>def primefactors(n, sort=False): factors = [] limit = int(n ** .5) + 1 for checker in smallprimes: print smallprimes[-1] if checker > limit: break while n % checker == 0: factors.append(checker) n //= checker if n < 2: return factors else : factors.extend(bigfactors(n,sort)) return factors def bigfactors(n, sort = False): factors = [] while n > 1: if isprime(n): factors.append(n) break factor = pollard_brent(n) factors.extend(bigfactors(factor,sort)) # recurse to factor the not necessarily prime factor returned by pollard-brent n //= factor if sort: factors.sort() return factors </code></pre> <p>By considering verified results of Pomerance, Selfridge and Wagstaff and Jaeschke, you can reduce the repetitions in <code>isprime</code> which uses Miller-Rabin primality test. From <a href="http://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test#Deterministic_variants_of_the_test" rel="noreferrer">Wiki</a>.</p> <ul> <li>if n < 1,373,653, it is enough to test a = 2 and 3;</li> <li>if n < 9,080,191, it is enough to test a = 31 and 73;</li> <li>if n < 4,759,123,141, it is enough to test a = 2, 7, and 61;</li> <li>if n < 2,152,302,898,747, it is enough to test a = 2, 3, 5, 7, and 11;</li> <li>if n < 3,474,749,660,383, it is enough to test a = 2, 3, 5, 7, 11, and 13;</li> <li>if n < 341,550,071,728,321, it is enough to test a = 2, 3, 5, 7, 11, 13, and 17.</li> </ul> <p><strong>Edit 1</strong>: Corrected return call of <code>if-else</code> to append bigfactors to factors in <code>primefactors</code>.</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