素数とか（雑）

primes.hs

-- author: Leonardone @ NEETSDKASU

isPrime :: Int -> Bool; primes :: [Int]

isPrime n = all (\e -> mod n e /= 0) $ takeWhile ((<=n).(^2)) primes

primes = 2 : 3 : filter isPrime os
    where
        os = zipWith (+) vs es
        vs = 6 : 6 : map (+6) vs
        es = cycle [-1,  1]




primeTool n = do
    table <- newArray (0,n+6) False :: IO (IOUArray Int64 Bool)
    primes <- newIORef [3,2]
    forM_ [1..((n+5) `div` 6)] $ \i -> do
        let x = 6*i - 1
        r <- readArray table x
        unless r $ do
            modifyIORef primes (x:)
            forM_ [3,5..((n+5) `div` x)] $ \k -> do
                writeArray table (k*x) True
        let y = x + 2
        q <- readArray table y
        unless q $ do
            modifyIORef primes (y:)
            forM_ [3,5..((n+5) `div` y)] $ \k -> do
                writeArray table (k*y) True
        writeArray table (y+2) True
    
    writeArray table 1 True
    table <- freeze table :: IO (UArray Int64 Bool)
    primes <- reverse <$> readIORef primes
    
    let isPrime v | even v = v == 2
                  | v < n  = not (table!v)
                  | otherwise = all ((/=0).mod v) $ takeWhile ((<=v).(^2)) primes
    
    return (primes, isPrime)