haskell - Haskell 中的半素数测试

Question

在调查 Arecibo message 时我试图实现 semiprimality在 Haskell 中测试。我提出了两个版本:

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 )运行了一些基准测试，结果 isSemiprime2 稍微快一些。你能想出一些更聪明的实现吗，因为我认为这不是最好的 :)。我对简洁、功能强大的实现特别感兴趣。

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

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

您列出的两个函数具有相同的性能，因为它们都使用 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 毫秒