检查整数（或整数列表中的所有元素）是否为素数 [英] Check whether an integer (or all elements of a list of integers) be prime
问题描述
我正在使用递归做一个简单的Haskell函数。目前，这似乎工作，但如果我输入 2 ，它实际上会出现错误，这是令人烦恼的。我认为代码没有那么好，所以，如果你有任何建议，那也会很酷！
我很漂亮新语言！
编辑：好吧，我明白一个素数是什么。
例如例如，我希望能够检查2,3,5,7等，并且有 isPrime 返回 true 。当然，如果我使用1,4,6,8等运行函数，那么它将返回 false 。
所以，我的想法是，在伪代码中，我需要做如下操作：
num = 2 - >返回true
num> 2&& num = even - >返回false
之后，我努力在任何工作代码中写下它，所以下面的代码我的工作正在进行中，但我真的很喜欢Haskell，所以我现在无处可去。
module递归其中
isPrime :: Int - > Bool
isPrime x = if x> 2（（x`mod`（x-1））/ = 0）&& not（isPrime（x-1））else False
好的，
让我们一步一步来做：
数学a（自然）数字<$ c $如果它有2个除数：1和它本身（头脑1不是素数），那么c> n 就是素数。
所有数字的除数：
divisors :: Integer - > [整数]
除数n = [d | d < - [1..n]，n`mod`d == 0]
然后得到它们的计数：
divisorCount :: Integer - > Int
divisorCount =长度。除数
瞧，我们使用定义最简单的实现：
isPrime :: Integer - > Bool
isPrime n = divisorCount n == 2
现在当然可以有相当多的改正：
- 改为检查是否没有除数
> 1和< n - 您不必检查所有除数
n-1，这足以请检查n的平方根。 - ...
好吧，高性能版本和使@Jubobs高兴;）这是一个替代方案：
isPrime :: Integer - > Bool
isPrime n
| n< = 1 = False
|否则=不。任何除以$ [2..sqrtN]
，其中除以d = n`mod`d == 0
sqrtN = floor。 sqrt $ fromIntegral n
这个将检查 2之间没有除数和数字的平方根
完整代码：
使用quickcheck进行制作确定这两个定义是正确的：
module Prime其中
import Test.QuickCheck
divisors :: Integer - > [整数]
除数n = [d | d< - [1..n]，n'mod'd == 0]
divisorCount :: Integer - > Int
divisorCount =长度。除数
isPrime :: Integer - > Bool
isPrime n
| n< = 1 = False
|否则=不。任何除以$ [2..sqrtN]
，其中除以d = n`mod`d == 0
sqrtN = floor。 sqrt $ fromInteral n
isPrime':: Integer - >布尔
isPrime 'N = divisorCount n ==可2
主:: IO（）
主要=快速检查（\\\
- > isPrime' N == isPrime n）的
!!警告!!
I刚才看到了（在我的脑海中有一些东西），我做了 sqrtN 不是最好的方式 - 抱歉。我认为在这里有小数字的例子没有问题，但也许你真的想使用类似的东西（从链接中）：
（^！）:: Num a => a - > Int - > a
（^！）x n = x ^ n
squareRoot :: Integer - >整数
对squareRoot 0 = 0
对squareRoot 1 = 1
对squareRoot N =
让twopows =迭代（^！2）2
（lowerRoot，lowerN）=
最后$ takeWhile（第（n> =）SND）$拉链（1：twopows）twopows
newtonStep X = DIV（X + DIV NX）2
iters =迭代newtonStep（对squareRoot（DIVñ lowerN）* lowerRoot）
isRoot r = r ^！2< = n&& n< （不包括isRoot）iters
I'm doing a simple Haskell function using recursion. At the moment, this seems to work but, if I enter 2, it actually comes up as false, which is irritating. I don't think the code is as good as it could be, so, if you have any advice there, that'd be cool too!
I'm pretty new to this language!
EDIT: Ok, so I understand what a prime number is.
For example, I want to be able to check 2, 3, 5, 7, etc and have isPrime return true. And of course if I run the function using 1, 4, 6, 8 etc then it will return false.
So, my thinking is that in pseudo code I would need to do as follows:
num = 2 -> return true
num > 2 && num = even -> return false
After that, I'm struggling to write it down in any working code so the code below is my work in process, but I really suck with Haskell so I'm going nowhere at the minute.
module Recursion where
isPrime :: Int -> Bool
isPrime x = if x > 2 then ((x `mod` (x-1)) /= 0) && not (isPrime (x-1)) else False
Ok,
let's do this step by step:
In math a (natural) number n is prime if it has exactly 2 divisors: 1 and itself (mind 1 is not a prime).
So let's first get all of the divisors of a number:
divisors :: Integer -> [Integer]
divisors n = [ d | d <- [1..n], n `mod` d == 0 ]
then get the count of them:
divisorCount :: Integer -> Int
divisorCount = length . divisors
and voila we have the most naive implementation using just the definition:
isPrime :: Integer -> Bool
isPrime n = divisorCount n == 2
now of course there can be quite some impprovements:
- instead check that there is no divisor
> 1and< n - you don't have to check all divisors up to
n-1, it's enough to check to the squareroot of n - ...
Ok just to give a bit more performant version and make @Jubobs happy ;) here is an alternative:
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
This one will check that there is no divisor between 2 and the squareroot of the number
complete code:
using quickcheck to make sure the two definitions are ok:
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)
!!warning!!
I just saw (had something in the back of my mind), that the way I did sqrtN is not the best way to do it - sorry for that. I think for the examples with small numbers here it will be no problem, but maybe you really want to use something like this (right from the link):
(^!) :: 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
but this seems a bit heavy for the question on hand so I just remark it here.
这篇关于检查整数（或整数列表中的所有元素）是否为素数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
