Download packages/mp-analytic/src/MP/Primes.hs from SNAPKITTYWEST/montrepol: direct link, hf CLI and curl.
- Browser
- Download file 2.21 kB
-
https://huggingface.co/SNAPKITTYWEST/montrepol/resolve/main/packages/mp-analytic/src/MP/Primes.hs
- Command line
-
hf download hf://SNAPKITTYWEST/montrepol/packages/mp-analytic/src/MP/Primes.hs
-
curl -L -o Primes.hs https://huggingface.co/SNAPKITTYWEST/montrepol/resolve/main/packages/mp-analytic/src/MP/Primes.hs
2.21 kB
| -- SPDX-License-Identifier: AGPL-3.0-or-later | |
| -- | Primes, the von Mangoldt function and Chebyshev's psi. | |
| -- | |
| -- @psi(x) = sum_{n <= x} Lambda(n)@, where @Lambda(p^k) = log p@ and is zero | |
| -- off prime powers. Exponentiating, @e^psi(x) = lcm(1, ..., x)@, which is an | |
| -- identity between integers and is what the tests check: it pins down | |
| -- 'primePowerBase' without any floating point. | |
| module MP.Primes | |
| ( primesUpTo | |
| , isPrimeTrial | |
| , primePowerBase | |
| , vonMangoldt | |
| , chebyshevPsi | |
| , primePowerProduct | |
| , primeCount | |
| ) where | |
| import Control.Monad (forM_, when) | |
| import Data.Array.ST (newArray, readArray, runSTUArray, writeArray) | |
| import Data.Array.Unboxed (UArray, assocs) | |
| -- | Sieve of Eratosthenes. | |
| primesUpTo :: Int -> [Int] | |
| primesUpTo n | |
| | n < 2 = [] | |
| | otherwise = [i | (i, True) <- assocs sieve] | |
| where | |
| sieve :: UArray Int Bool | |
| sieve = runSTUArray $ do | |
| arr <- newArray (2, n) True | |
| forM_ (takeWhile (\i -> i * i <= n) [2 ..]) $ \i -> do | |
| isP <- readArray arr i | |
| when isP $ forM_ [i * i, i * i + i .. n] $ \j -> writeArray arr j False | |
| pure arr | |
| -- | Trial division: slow, obviously correct, the oracle for the sieve. | |
| isPrimeTrial :: Int -> Bool | |
| isPrimeTrial n = n >= 2 && all (\d -> n `mod` d /= 0) (takeWhile (\d -> d * d <= n) [2 ..]) | |
| -- | @Just p@ when @n = p^k@ for a prime @p@ and @k >= 1@. | |
| primePowerBase :: Int -> Maybe Int | |
| primePowerBase n | |
| | n < 2 = Nothing | |
| | otherwise = | |
| let p = smallestFactor n | |
| in if strip p n == 1 then Just p else Nothing | |
| where | |
| smallestFactor m = case [d | d <- takeWhile (\d -> d * d <= m) [2 ..], m `mod` d == 0] of | |
| (d : _) -> d | |
| [] -> m | |
| strip p m = if m `mod` p == 0 then strip p (m `div` p) else m | |
| vonMangoldt :: Int -> Double | |
| vonMangoldt = maybe 0 (log . fromIntegral) . primePowerBase | |
| -- | @psi(x)@ for real @x@: the sum over @n <= floor x@. | |
| chebyshevPsi :: Double -> Double | |
| chebyshevPsi x = sum (map vonMangoldt [2 .. floor x]) | |
| -- | @prod_{p^k <= x} p@, exactly; equal to @lcm(1, ..., x)@. | |
| primePowerProduct :: Int -> Integer | |
| primePowerProduct x = product [toInteger p | n <- [2 .. x], Just p <- [primePowerBase n]] | |
| primeCount :: Int -> Int | |
| primeCount = length . primesUpTo | |