Semiprime number test in Haskell

Question

While investigating the Arecibo message I tried to implement semiprimality tests in Haskell. I've come 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 ran some benchmarks using defaultMain (from the package Criterion.Main) and isSemiprime2 turned out slightly faster. Can you think of some more clever implementations, cause I don't think this is the cream of the crop :). I'm specifically interested in concise, heavily functional implementations.

Also, if anyone is interested, here's 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
                              ]
       ]

Answer 1

The two functions you listed have the same performance since they both use primeFactors where most of the time is spent. If you look at the implementation it's just doing trial division with successive numbers generated from the sieve. This is not the most efficient method.

If you want faster code you should use a better factorization algorithm. For example:

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

results in:

....
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 ms vs. 138 ms

Answer 2

i used this code to find semiPrime between a to b, is not the best, but works, was for a interview in js

function findSemiprimes(rangeStart, rangeEnd) {
  let inicio = rangeStart
  let final = rangeEnd
  if (final < inicio) {
    inicio = rangeEnd
    final = rangeStart
  }
  let primos = []
  for (let i = 1; i <= final; i++) {
    if (isPrime(i)) {
      primos.push(i)
    }
  }

  let semiPrimos = []

  for (const primo of primos) {
    let primos2 = []
    for (let i = 2; i <= primo; i++) {
      if (isPrime(i)) primos2.push(i)
    }
    for (const primo2 of primos2) {
      let posible = primo * primo2
      if (posible <= final) {
        if (semiPrimos.indexOf(posible) <= 0) {
          semiPrimos.push(posible)
        }
      }
    }

  }

  semiPrimos.sort(function (a, b) {
    return a - b;
  })
  semiPrimos = semiPrimos.filter(primo => primo >= inicio)
  return semiPrimos
}


function isPrime(num) {
  for (var i = 2; i < num; i++) {
    if (num % i === 0) {
      return false;
    }
  }
  return num !== 1;
}

function main() {
  const result = findSemiprimes(20, 100);
  console.log("result:", result)
}

main()