17

そのため、特定の数値が Haskell で素数であるかどうかを確認するために、次の関数を考案しました (最初の素数が 2 であると想定しています)。

isPrime k = length [ x | x <- [2..k], k `mod` x == 0] == 1

いくつかの数で割り切れる場合でも、評価を継続するという明らかな落とし穴があります:(。リスト内包表記を使用して、複数の解が見つかったときに評価を「カット」する適切な方法はありますか?

また、他にどの実装を試しますか? 私はここでパフォーマンスを探しているわけではありません。同じことを行う他の「ハスケル」の方法があるかどうかを確認しようとしているだけです。

4

6 に答える 6

31

評価を「短絡」し、Haskell リストの遅延に依存するコードへの簡単な変更は次のとおりです。

isPrime k = if k > 1 then null [ x | x <- [2..k - 1], k `mod` x == 0] else False

の一番最初の除数によってkリストが空ではなくなり、 の Haskell 実装はnullリストの最初の要素だけを調べます。

sqrt(k)ただし、確認する必要があるのは次のとおりです。

isPrime k = if k > 1 then null [ x | x <- [2..isqrt k], k `mod` x == 0] else False

もちろん、高性能の素数性テストを行う場合は、ライブラリを使用することをお勧めします。

于 2011-01-14T19:19:57.760 に答える
12

haskell.orgの haskellの素数の最適なリソースは次のとおりです。

ここでは、prime.hs github プロジェクト

于 2011-01-14T12:07:57.670 に答える
7

直接関係はないかもしれませんが、関数型言語で素数を見つけるというトピックについては、メリッサE.オニールのエラトステネスの本物のふるいが非常に興味深いと思いました。

于 2011-01-14T12:00:07.223 に答える
6

私はこのアプローチが好きです：

まず、n のすべての因数を取得する関数を作成します。

factors n = [x | x <- [1..n], mod n x == 0]

次に、約数が指定された数と 1 のみであるかどうかを確認します。そうであれば、その数は素数です。

prime n = factors n == [1,n]
于 2016-05-09T18:46:07.083 に答える
4

素数の問題を無視し、 のより効率的な方法の狭点に焦点を当てますlength xs == n。

hasLength :: Integral count => [a] -> count -> Bool
_        `hasLength` n | n < 0 = False
[]       `hasLength` n         = n == 0
(_ : xs) `hasLength` n         = xs `hasLength` (pred n)

isPrime k = [ x | x <- [2..k], k `mod` x == 0)] `hasLength` 1
于 2011-01-14T12:34:27.070 に答える