检查整数(或整数列表的所有元素)是否为素数

Question

我正在使用递归来做一个简单的Haskell函数.目前,这似乎有效,但是,如果我进入2,它实际上是虚假的,这是令人恼火的.我认为代码不尽如人意,所以,如果你有任何建议,那也很酷!

我对这门语言很陌生!

编辑:好的,所以我理解素数是多少.

例如,我希望能够检查2,3,5,7等,并isPrime返回true.当然,如果我使用1,4,6,8等运行该功能,那么它将返回false.

所以,我的想法是在伪代码中我需要做如下:

num = 2 -> return true
num > 2 && num = even -> return false

在那之后,我很难在任何正常工作的代码中写下来,所以下面的代码是我正在进行的工作,但我真的很厌烦Haskell所以我现在无处可去.

module Recursion where

isPrime :: Int -> Bool
isPrime x = if x > 2 then ((x `mod` (x-1)) /= 0) && not (isPrime (x-1)) else False

Answer 1

好,

让我们一步一步来做:

在数学中,如果一个(自然)数字n恰好有2个除数:1和它本身(思想1不是素数),则它是素数.

所以让我们先得到一个数字的所有除数:

divisors :: Integer -> [Integer]
divisors n = [ d | d <- [1..n], n `mod` d == 0 ]

然后得到他们的数量:

divisorCount :: Integer -> Int
divisorCount = length . divisors

并且我们只使用定义来实现最天真的实现:

isPrime :: Integer -> Bool
isPrime n = divisorCount n == 2

现在当然可能会有一些不足之处:

• 而是检查没有除数> 1和< n
• 你不必检查所有除数n-1,它足以检查n的平方根
• ...

好的只是为了提供更高性能的版本并让@Jubobs满意;)这里有一个替代方案:

isPrime :: Integer -> Bool
isPrime n
  | n <= 1 = False
  | otherwise = not . any divides $ [2..sqrtN]
  where divides d = n `mod` d == 0
        sqrtN = floor . sqrt $ fromIntegral n

这个将检查2数字的平方根和数字的平方根之间没有除数

完整代码:

使用quickcheck确保两个定义正常:

module Prime where

import Test.QuickCheck

divisors :: Integer -> [Integer]
divisors n = [ d | d <- [1..n], n `mod` d == 0 ]

divisorCount :: Integer -> Int
divisorCount = length . divisors

isPrime :: Integer -> Bool
isPrime n
  | n <= 1 = False
  | otherwise = not . any divides $ [2..sqrtN]
  where divides d = n `mod` d == 0
        sqrtN = floor . sqrt $ fromIntegral n

isPrime' :: Integer -> Bool
isPrime' n = divisorCount n == 2

main :: IO()
main = quickCheck (\n -> isPrime' n == isPrime n)

!!警告!!

我刚刚看到(脑子里有些东西),我做的方式sqrtN 不是最好的方法 - 对不起.我认为这里的小数字的例子没有问题,但也许你真的想要使用这样的东西(直接来自链接):

(^!) :: Num a => a -> Int -> a
(^!) x n = x^n

squareRoot :: Integer -> Integer
squareRoot 0 = 0
squareRoot 1 = 1
squareRoot n =
   let twopows = iterate (^!2) 2
       (lowerRoot, lowerN) =
          last $ takeWhile ((n>=) . snd) $ zip (1:twopows) twopows
       newtonStep x = div (x + div n x) 2
       iters = iterate newtonStep (squareRoot (div n lowerN) * lowerRoot)
       isRoot r  =  r^!2 <= n && n < (r+1)^!2
   in  head $ dropWhile (not . isRoot) iters

但这对于手头的问题似乎有点沉重,所以我只是在这里说.