Haskell中的半素数检验

Question

[调查Arecibo message时，我试图在Haskell中实现semiprimality测试。我想出了两个版本：

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

我使用defaultMain（来自Criterion.Main包）运行了一些基准测试，Criterion.Main的运行速度稍快。您能想到一些更聪明的实现，因为我认为这不是问题的关键：)。我对简洁，功能强大的实现特别感兴趣。

此外，如果有人感兴趣，这是我的基准测试代码：

isSemiprime2

Answer 1

您列出的两个功能具有相同的性能，因为它们都使用

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
                              ]
       ]

来花费大部分时间。如果您看一下实现，它只是用筛子生成的连续数字进行试除。这不是最有效的方法。

如果您想要更快的代码，则应使用更好的分解算法。例如：

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

5毫秒vs. 138毫秒

Answer 2

我用这段代码在a到b之间找到了半素，这不是最好的，但是可以用js进行采访

....
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