Name: Anonymous 2009-03-17 8:22
It took the python interpreter fucking 100 minutes to print all the indentation errors for my first attempt at this.
Insane indentation style is fucking insane.
I finally got it work, but it's ugly as hell and slow as slightly faster than usual fuck:
Insane indentation style is fucking insane.
I finally got it work, but it's ugly as hell and slow as slightly faster than usual fuck:
import math
from itertools import takewhile, dropwhile
def eratosthenes():
D = {}
q = 2
while 1:
if q not in D:
yield q
D[q*q] = [q]
else:
for p in D[q]:
D.setdefault(p+q,[]).append(p)
del D[q]
q += 1
def bitcount(n):
r = 0;
while n > 0:
r += n & 1
n >>=1
return r
def take(n, g):
for i in range(n): yield g.next()
def swing(n):
primes = list(takewhile(lambda x: x <= n, eratosthenes()))
smalloddswing = [1,1,1,3,3,15,5,35,35,315,63,693,231,3003,429,6435,6435,109395,12155,230945,46189,969969,88179,2028117,676039,16900975,1300075,35102025,5014575,145422675,9694845,300540195,300540195]
if n < 33: return smalloddswing[n]
primelist = []
rootn = long(math.sqrt(n))
primesa = takewhile(lambda x: x <= rootn, dropwhile(lambda x: x < 3, primes))
primesb = takewhile(lambda x: x <= n // 3, dropwhile(lambda x: x <= rootn, primes))
for prime in primesa:
q = n // prime
p = 1
while q > 0:
if q & 1 == 1: p *= prime
q //= prime
if p > 1: primelist.append(p)
return reduce(lambda x, y: x * y, list(takewhile(lambda x: x <= n, dropwhile(lambda x: x <= n // 2, primes))) + primelist + filter(lambda x: n // x & 1 == 1, primesb), 1)
def recfactorial(n):
if n < 2: return 1
return recfactorial(n // 2) ** 2 * swing(n)
def factorial(n):
if n < 20: return reduce(lambda x, y: x * y, range(2,n + 1), 1)
return recfactorial(n) << (n - bitcount(n))