Haskell Prime测试混乱

Question

所以我对Haskell完全不熟悉,希望它不会显示太多.无论如何,我试图创建一个函数来确定一个数字是否为素数.基本思路是这样的:给定一个数字,看看它是否可被任何小于它的任何其他数字整除.如果是,则返回false.如果不是,它是素数,返回真实.到目前为止的代码(已知有效)是这样的:

divisible :: Integer -> Integer -> Bool
divisible x 2 = even x
divisible x y = ((x `mod` y) /= 0) && not (divisible x (y-1))
isPrime :: Integer -> Bool
isPrime x = not (even x) && not (divisible x (x-1))

生产:

ghci> isPrime 9
False
ghci> isPrime 13
True

我想做的是稍微优化一下,因为我只需要检查小于或等于sqrt(x)的值.问题是,当我尝试实现这个时,东西变得疯狂:

isPrime x = not (even x) && not (divisible x (ceiling(sqrt(fromIntegral(x-1)))))

除了它看起来很糟糕的事实(我说我是新的),它没有给出正确的结果:

ghci> isPrime 9
False
ghci> isPrime 13
False

我想弄清楚改变了什么,因为:

ghci> ceiling(sqrt(13))
4

似乎给了我正确的号码.我知道这是一个小问题,但我很困惑......

Answer 1

你的条件混乱了:

divisible x y = ((x `mod` y) /= 0) && not (divisible x (y-1))

应该

divisible x y = (x `mod` y) == 0 || divisible x (y-1)

为了测试工作.

就像你的divisible功能扩展一样

divisible 21 5 = (21 `mod` 5 /= 0) && not (divisible 21 4)
               = (21 `mod` 5 /= 0) && not ((21 `mod` 4 /= 0) && not (divisible 21 3))
               = not ((21 `mod` 4 /= 0) && not ((21 `mod` 3 /= 0) && not (divisible 21 2)))
               = not (True && not (False && not (divisible 21 3)))
               = not (not False)
               = False

因为21 `mod` 3 == 0,并用平方根绑定isPrime 21进行评估True.

但是,我明白了

*StrangePrime> isPrime 9
True
*StrangePrime> isPrime 13
True

用你的代码使用平方根.

如果没有平方根,它恰好适用于奇数,因为奇数复数与其任何除数之间的差异始终是偶数.我们看到,展开divisible几步n = p*m,其中p是奇数复合材料的最小素因子n

divisible n (n-1) = n `mod` (n-1) /= 0 && not (divisible n (n-2))
                  = not (divisible n (n-2))
                  = not (n `mod` (n-2) /= 0 && not (divisible n (n-3)))
                  = not (not (divisible n (n-3)))
                  = not^2 (divisible n (n-3))

和归纳

divisible n (n-1) = not^(k-1) (divisible n (n-k))

如果没有n大于的除数n-k.现在,在上述情况下,最大的除数n是m = n - (p-1)*m,所以我们得到了

divisible n (n-1) = not^((p-1)*m-1) (divisible n m)
                  = not^((p-1)*m-1) (n `mod` m /= 0 && not (...))

但是n `mod` m == 0,我们有

divisible n (n-1) = not^((p-1)*m-1) False

因为p是奇数,p-1是偶数,所以也是如此(p-1)*m,所以我们总共有一个奇数个nots,它与一个相同not,给出

divisible n (n-1) = True
isPrime n = not (even n) && not (divisible n (n-1)) = True && not True = False

如果p是一个奇数素数,展开到达divisible p (p-1) = not^(p-3) (divisible p (p - (p-2))).p-3是,divisible p 2是,是even p,是False.

一般来说,考虑divisible n s一个奇数n,并且让它d成为n不超过的最大除数s,如果n是复合的,或者d = 2如果n是素数.展开divisible n s仍然以同样的方式进行

divisible n s = not^k (divisible n (s-k))

虽然没有找到除数s-k > 2.因此,对于复合材料n,我们发现

divisible n s = not^(s-d) (divisible n d)
              = not^(s-d) (n `mod` d /= 0 && not (...))
              = not^(s-d) False
              = odd (s-d)
              = even s     -- since d is odd, as a divisor of an odd number

在奇数素数的情况下n,

divisible n s = not^(s-2) (divisible n 2)
              = not^(s-2) (even n)
              = not^(s-2) False
              = odd s

因此,divisible n s测量s到下一个较小除数的距离的平价n或为2,取较大者.什么s时候n-1,起始点始终是偶数,所以它正确地计算出来,但ceiling (sqrt (fromIntegral (n-1)))可能很奇怪,在这种情况下,结果被翻转,复合材料被声明为素数,反之亦然.

divisible如果你确保第一个调用得到一个偶数第二个参数(所以如果ceiling (sqrt (fromIntegral (n-1)))是奇数,从那里开始ceiling (sqrt (fromIntegral (n-1))) + 1),你可以使你的函数适用于具有平方根界限的奇数的素性测试,但是该函数的逻辑令人困惑,并且其名称未正确描述其结果.

写一个更惯用的方法就是

isPrime n = and [n `mod` k /= 0 | k <- [2 .. ceiling (sqrt $ fromIntegral n)]]

当一个跳过已经被认为是先前测试中的非导数的候选除数时,测试变得更有效,很容易跳过除2之外的所有偶数,

isPrime 2 = True
isPrime n = all ((/= 0) . (n `mod`)) (2 : [3, 5 .. ceiling (sqrt (fromIntegral n))])

稍微多一些,但更高效也是跳过3的倍数

isPrime n = all ((/= 0) . (n `mod`)) (takeWhile (<= bound) (2:3:scanl (+) 5 (cycle [2,4])))
  where
    bound = ceiling (sqrt (fromIntegral (n-1)))

同样可以从试验除数中消除多个较小的素数,每个都获得了一点效率,但是以更复杂的轮子为代价,例如也消除了5的倍数导致

isPrime n = all ((/= 0) . (n `mod`)) (takeWhile (<= bound) (2:3:5: scanl (+) 7 (cycle [4,2,4,2,4,6,2,6])))
  where
    bound = ceiling (sqrt (fromIntegral (n-1)))