0hc.net Menu
Home Overview
About Menu
Impressum

Prime Swing algorithm

import System.Environment import Data.Binary import Data.Bits import Math.NumberTheory.Primes import Math.NumberTheory.Powers import Math.NumberTheory.Logarithms main = getArgs >>= \[f,n]-> encodeFile f $ fac $ read n fac x = shift (rec x) (fromIntegral x-bits x) bits x = foldl (\a b->a+fromEnum (testBit x b)) 0 [0..integerLog2 x+1] rec 1 = 1 rec x = (rec $ x`quot`2)^2*sw x sw x | x<33 = oSwing!!fromIntegral x | otherwise = product p3 * product (pa p1) * product (pb p2) where s = integerSquareRoot x p1 = takeWhile (<=s) $ drop 1 primes p2 = takeWhile (<=x`quot`3) $ dropWhile (<=s) primes p3 = takeWhile (<=x) $ dropWhile (<=x`quot`2) primes pa = f [] where f xs [] = xs f xs (a:as) = let (n,_) = oT (1,x) a in if n > 1 then f (n:xs) as else f xs as pb = filter (odd . quot x) oT (a,b) x = let q = b`quot`x in if q==0 then (a,b) else if odd q then oT (a*x,q) x else oT (a,q) x oSwing = [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]
0hc.net    © 2001-2014 Harald Wolfsgruber