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)

MacにHaskellコンパイラがないため、Cでアルゴリズムをテストしましたが、で誤検知が返されるため、何か問題がありprimes-1ます。idkなぜ。

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. sqrthoogle http://www.haskell.org/hoogle/のような関数を検索します
  5. IntegerHaskell は静的に型付けされるため、との間でいくつかの数値型を変換する必要があります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

（明らかに、宿題に関する新しいポリシーがあります。つまり、「完全に精査された、完全でテスト可能な回答が必要ない場合は、スタックオーバーフローは質問する場所ではありません-ティムポストによる」なので、ここに行きます）。

基本的に、あなたのコードはほとんど正しいです (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引数として値を使用できるようにする単なるアダプターです。GHCi プロンプトでorなどを使用してみてください(また、いくつかのドキュメントgoogle around を読んでください)。sqrtFloating:i sqrt:i Integral

しかし、アルゴリズム的には改善の余地があります。まず第一に、2 から数値の まで、逆方向の除数を試す方がはるかに優れています。これはsqrt、与えられた数値は、大きい因数よりも小さい因数を持つ可能性が高いためです。第 2 に、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)

Boolこれは通常、s と、再帰とテスト パターンをキャプチャするような高階関数を使用して書き留められ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..])
       ...........

ここで、エラトステネスのふるいP = {3,5, ...} \ U {{ p 2 , p 2 + 2p, ...}の出現が見られます。p in P } (なし2)。

以下も参照してください。

于 2012-09-15T09:11:44.927 に答える