1

我需要实现一个递归函数，如果数字是素数则返回 1，否则返回 0。作业问题说我不能使用 '%' mod。Haskell应该是这样的......我不确定。

isprime x = prime(x sqrt(x))

prime x i = | i==1 = 1
            | mod(x i)==0 = 0
            | otherwise = prime(x i-1)

mod num div | num<div = n
            | otherwise = mod(num-div div)

我在 C 中测试了一个算法，因为我的 Mac 上没有 Haskell 编译器，但是出现了问题，因为它在primes-1. 我知道为什么。

int main (int argc, const char * argv[]){
    int a=0,b=31;
    printf("\n Prime numbers between %d and %d \n",a,b);

    for(int a=0; a<=b; a++){
        if(isPrime(a)==0){
            printf("%d, ",a);
        } 
    }
    return 0;
}

int isPrime(int x){
    return prime(x, sqrt(x));
}

int prime(int x, int i){
    if(i==0){
        return 0;
    }
    else if(mod(x,i)==1){
        return 1;
    }
    else{
        return prime(x, i-1);
    }
}

int mod(int num, int div){
    if(num<div) return num;
    else return mod(num-div, div);
}

算法返回这个：

Prime numbers between 0 and 31 
0, 1, 2, 3, 4, 6, 8, 12, 14, 18, 20, 24, 30,
Program ended with exit code: 0
4

3 回答 3

5

你的基本想法很好。在 Haskell 中，您可以使用列表而不是迭代。以下是您需要调查的内容：

  1. 安装并使用 ghci。
  2. 如果你不知道如何在 Haskell 中做任何事情，请访问Learn You a Haskell for Great Good http://learnyouahaskell.com/
  3. 列出理解。了解[n^2 | n <- [1..10]]含义并使用类似的列表。
  4. sqrt在hoogle http://www.haskell.org/hoogle/上查找功能
  5. 因为 Haskell 是静态类型的，你需要在Integer和之间转换一些数字类型Float。抬头看看你什么Float -> Integer时候Integer -> Float做。不要使用unsafeCoerce- 它不安全并且会严重破坏事物。
  6. 使用 hoogle 查找[Bool] -> Bool。我为什么这么建议？会有什么[Bool]帮助，无论如何你会怎么做？（再次修改列表理解。）
  7. 了解更多信息并尝试后，请返回更具体的问题。
  8. 总是尽早开始你的作业，特别是如果你错过了课程！

你被设置这个作业不是因为部门被困在决定 102659473841923461 是否是素数的方法上，而是因为他们希望你学习一些 Haskell。尽量不要在不学习的情况下尝试解决问题——这只会使下一个任务变得更加困难！（这就是为什么我抵制将另一个答案中的“伪代码”翻译成 Haskell 的原因。）

于 2012-09-13T22:30:19.303 回答
1

我不知道 Haskell，也不想给你答案，但我可以提供一个方法。

如果您检查从 2 到 sqrt(n) 的所有数字，并且它们都不是 n 的因数，则 n 是素数。

因此，使用以下伪代码的函数调用可能会起作用：

def isPrime(n):
   return isPrimeHelper(n,sqrt(n))

def isPrimeHelper(n,counter):
   if counter == 1 return True
   if n % counter == 0 return False
   else return isPrime(n,counter-1)
于 2012-09-13T22:10:25.507 回答
1

（显然，有一个关于家庭作业的新政策，即“如果你不想要一个经过全面审查、完整和可测试的答案，Stack Overflow 不是问的地方——Tim Post”，所以这里是）。

基本上，您的代码几乎是正确的（1不是素数），没有一些语法问题。

isprime x = prime x (floor $ sqrt $ fromIntegral x)   where
  prime x i | i==1 && x > 1  = 1
            | x == i*div x i = 0
            | otherwise      = prime x (i-1)

-- mod x i = x - i*div x i
-- mod x i == 0 = x == i*div x i

fromIntegral只是一些适配器，它允许我们使用一个Integral值作为参数，sqrt它需要一个 Floating参数。尝试在 GHCi 提示符下使用:i sqrtor等​​（也可以阅读一些文档google）。:i Integral

但在算法上还有改进的地方。首先，最好从另一个方向尝试除数，从 2 到 number's sqrt，因为任何给定的数字都更有可能具有较小的因数而不是较大的因数。其次，在尝试了 2 之后，没有必要尝试任何其他偶数作为可能的除数。这给了我们

isprime x | x == 2          = 1
          | x < 2 || even x = 0
          | otherwise       = go 3
  where
    r = floor $ sqrt $ fromIntegral x
    go i | i > r          = 1
         | x == i*div x i = 0        -- really, | rem x i == 0 = 0
         | otherwise      = go (i+2)

这通常会使用Bools 和一个高阶函数（如and捕获递归和测试模式）来写下来（因此它不再是递归的）：

isprime x = if isPrime x then 1 else 0

isPrime x = x==2 || x>2 && odd x && 
              and [rem x d /= 0 | d <- [3,5..floor $ sqrt $ fromIntegral x]]

仍然有一些冗余：在我们测试了 3 之后，也不需要测试它的任何倍数（就像我们对 2 和偶数所做的那样）。我们真的只需要通过主要因素进行测试：

isPrime x = x>1 && and 
    [rem x d /= 0 | d <- takeWhile (<= (floor $ sqrt $ fromIntegral x)) primes]

primes = filter isPrime [2..]
       = 2 : filter isPrime ([3..] `minus` [4,6..])
       = 2 : filter isPrime [3,5..]
       = 2 : 3 : filter isPrime ([5,7..] `minus` [9,15..])
       = 2 : 3 : 5 : filter isPrime (([7,9..]`minus`[9,15..])`minus`[25,35..])
       ...........

这里我们看到了 Eratosthenes 筛的出现，P = {3,5, ...} \ U {{ p 2 , p 2 + 2p, ...} | p中的p }（不包含2）。

也可以看看：

于 2012-09-15T09:11:44.927 回答