prime swing algorithm python

1
21    import bisect 
32     
43    def Primes(n) : 
54        primes = [2, 3] 
65        lim, tog = n // 3, False 
76        composite = [False for i in range(lim)] 
87     
98        d1 = 8; d2 = 8; p1 = 3; p2 = 7; s = 7; s2 = 3; m = -1 
109     
1110       while s < lim :             # --  scan the sieve 
1211           m += 1                  # --  if a prime is found 
1312           if not composite[m] :   # --  cancel its multiples 
1413               inc = p1 + p2 
1514               for k in range(s,      lim, inc) : composite[k] = True 
1615               for k in range(s + s2, lim, inc) : composite[k] = True 
1716    
1817               tog = not tog 
1918               if tog: s += d2; d1 += 16; p1 += 2; p2 += 2; s2 = p2 
2019               else:   s += d1; d2 +=  8; p1 += 2; p2 += 6; s2 = p1 
2120    
2221       k, p, tog = 0, 5, False 
2322       while p <= n : 
2423           if not composite[k] : primes.append(p) 
2524           k += 1; 
2625           tog = not tog 
2726           p += 2 if tog else 4 
2827    
2928       return primes 
3029    
3130   def isqrt(x): 
3231       ''' 
3332       Writing your own square root function
3433       ''' 
3534       if x < 0: raise ValueError('square root not defined for negative numbers') 
3635       n = int(x) 
3736       if n == 0: return 0 
3837       a, b = divmod(n.bit_length(), 2) 
3938       x = 2**(a + b) 
4039       while True: 
4140           y = (x + n // x) // 2 
4241           if y >= x: return x 
4342           x = y 
4443            
4544   def product(s, n, m): 
4645       if n > m: return 1 
4746       if n == m: return s[n] 
4847       k = (n + m) // 2 
4948       return product(s, n, k) * product(s, k + 1, m) 
5049    
5150   def factorialPS(n): 
5251    
5352       small_swing = [1,1,1,3,3,15,5,35,35,315,63,693,231,3003,429,6435,6435, 
5453           109395,12155,230945,46189,969969,88179,2028117,676039,16900975, 
5554           1300075,35102025,5014575,145422675,9694845,300540195,300540195] 
5655    
5756       def swing(m, primes): 
5857           if m < 33: return small_swing[m] 
5958            
6059           s = bisect.bisect_left(primes, 1 + isqrt(m)) 
6160           d = bisect.bisect_left(primes, 1 + m // 3) 
6261           e = bisect.bisect_left(primes, 1 + m // 2) 
6362           g = bisect.bisect_left(primes, 1 + m) 
6463            
6564           factors = primes[e:g] 
6665           factors += filter(lambda x: (m // x) & 1 == 1, primes[s:d]) 
6766           for prime in primes[1:s]:   
6867               p, q = 1, m 
6968               while True: 
7069                   q //= prime 
7170                   if q == 0: break 
7271                   if q & 1 == 1: 
7372                       p *= prime 
7473               if p > 1: factors.append(p) 
7574    
7675           return product(factors, 0, len(factors) - 1) 
7776    
7877       def odd_factorial(n, primes): 
7978           if n < 2: return 1 
8079           return (odd_factorial(n // 2, primes)**2) * swing(n, primes) 
8180    
8281       def eval(n): 
8382           if n < 0: 
8483               raise ValueError('factorial not defined for negative numbers') 
8584    
8685           if n == 0: return 1 
8786           if n < 20: return product(range(2, n + 1), 0, n-2) 
8887    
8988           N, bits = n, n 
9089           while N != 0: 
9190               bits -= N & 1 
9291               N >>= 1 
9392    
9493           primes = Primes(n) 
9594           return odd_factorial(n, primes) * 2**bits 
9695    
9796       return eval(n) 
9897    
9998   factorialPS(100) 
100
101