Geek asks and answers

Haskell Seven Primary Number Test

While researching Arecibo posts, I tried to implement semiprimality tests in Haskell. I came up with two versions:

isSemiprime1 :: Int -> Bool
isSemiprime1 n = (length factors) == 2 && (product factors) == n ||
                (length factors) == 1 && (head factors) ^ 2 == n
                    where factors = primeFactors n

isSemiprime2 :: Int -> Bool
isSemiprime2 n =
            case (primeFactors n) of
              [f1, f2] -> f1 * f2 == n
              [f] -> f ^ 2 == n
              otherwise -> False

I used some tests using defaultMain(from the package Criterion.Main) and isSemiprime2it turned out a little faster. Can you think of smarter implementations because I don’t think this is a cream from the crop :). I am particularly interested in short, highly functional implementations.

Also, if anyone is interested, here is my code for benchmarking:

main :: IO ()
main = defaultMain [
        bgroup "isSemiprime1" [ bench "169" $ whnf isSemiprime1 169
                              , bench "1679" $ whnf isSemiprime1 1679
                              ],
        bgroup "isSemiprime2" [ bench "169" $ whnf isSemiprime2 169
                              , bench "1679" $ whnf isSemiprime2 1679
                              ]
       ]
+3
source share
1 answer

, primeFactors, . , , . .

, . :

import Math.NumberTheory.Primes.Factorisation

isSemiprime3 :: Integer -> Bool
isSemiprime3 n = (length factors) == 2 && (product factors) == n ||
                (length factors) == 1 && (head factors) ^ 2 == n
                    where factors = map fst $ factorise n

:

....
benchmarking isSemiprime1/557672900621
collecting 100 samples, 1 iterations each, in estimated 13.84439 s
mean: 138.4969 ms, lb 138.3753 ms, ub 138.7278 ms, ci 0.950
std dev: 830.8696 us, lb 505.2076 us, ub 1.301439 ms, ci 0.950

benchmarking isSemiprime3/557672900621
mean: 5.315161 ms, lb 5.292123 ms, ub 5.397730 ms, ci 0.950
std dev: 198.7367 us, lb 59.15932 us, ub 453.7225 us, ci 0.950
found 5 outliers among 100 samples (5.0%)
  3 (3.0%) high mild
  2 (2.0%) high severe
variance introduced by outliers: 33.631%
variance is moderately inflated by outliers

benchmarking isSemiprime2/557672900621
collecting 100 samples, 1 iterations each, in estimated 13.85570 s
mean: 138.9948 ms, lb 138.8015 ms, ub 139.3493 ms, ci 0.950
std dev: 1.302262 ms, lb 844.1709 us, ub 2.330201 ms, ci 0.950

5 138

+1

More articles:


All Articles