3

だから私はHaskellに全く慣れていないので、あまり表示されないことを願っています。とにかく、私は数が素数であるかどうかを判断する関数を作成しようとしていました。基本的な考え方は次のとおりです。数値が与えられたら、それよりも小さい他の数値で割り切れるかどうかを確認します。その場合、falseを返します。そうでない場合、それは素数であり、trueを返します。これまでのコード（動作していることがわかっている）は次のとおりです。

divisible :: Integer -> Integer -> Bool
divisible x 2 = even x
divisible x y = ((x `mod` y) /= 0) && not (divisible x (y-1))
isPrime :: Integer -> Bool
isPrime x = not (even x) && not (divisible x (x-1))

生産：

ghci> isPrime 9
False
ghci> isPrime 13
True

sqrt（x）以下の値をチェックするだけでよいので、これを少し最適化したいと思います。問題は、これを実装しようとすると、物事がおかしくなることです。

isPrime x = not (even x) && not (divisible x (ceiling(sqrt(fromIntegral(x-1)))))

それがひどいように見えるという事実（私は私が新しいと言った）に加えて、それは正しい結果を与えません：

ghci> isPrime 9
False
ghci> isPrime 13
False

何が変わったのかを理解しようとしています。理由は次のとおりです。

ghci> ceiling(sqrt(13))
4

正しい番号を教えてくれているようです。これは小さな問題ですが、私は真剣に混乱しています...

4

2 に答える 2

13

あなたはあなたの条件を混乱させました：

divisible x y = ((x `mod` y) /= 0) && not (divisible x (y-1))

する必要があります

divisible x y = (x `mod` y) == 0 || divisible x (y-1)

テストが機能するために。

そのまま、あなたのdivisible関数は例えば

divisible 21 5 = (21 `mod` 5 /= 0) && not (divisible 21 4)
               = (21 `mod` 5 /= 0) && not ((21 `mod` 4 /= 0) && not (divisible 21 3))
               = not ((21 `mod` 4 /= 0) && not ((21 `mod` 3 /= 0) && not (divisible 21 2)))
               = not (True && not (False && not (divisible 21 3)))
               = not (not False)
               = False

以来21 `mod` 3 == 0、平方根境界でisPrime 21評価します。True

しかし、私は

*StrangePrime> isPrime 9
True
*StrangePrime> isPrime 13
True

平方根を使用してコードを使用します。

平方根がないと、奇数の合成数とその除数の差は常に偶数であるため、たまたま奇数で機能しました。divisibleのいくつかのステップを展開しますn = p*m。ここで、pは奇数の合成の最小の素因数です。n

divisible n (n-1) = n `mod` (n-1) /= 0 && not (divisible n (n-2))
                  = not (divisible n (n-2))
                  = not (n `mod` (n-2) /= 0 && not (divisible n (n-3)))
                  = not (not (divisible n (n-3)))
                  = not^2 (divisible n (n-3))

そして帰納的に

divisible n (n-1) = not^(k-1) (divisible n (n-k))

nより大きい除数がない場合n-k。さて、上記の状況では、の最大の約数nはm = n - (p-1)*mであるため、次のようになります。

divisible n (n-1) = not^((p-1)*m-1) (divisible n m)
                  = not^((p-1)*m-1) (n `mod` m /= 0 && not (...))

しかしn `mod` m == 0、だから私たちは

divisible n (n-1) = not^((p-1)*m-1) False

pは奇数であるため、偶数p-1であり、したがって、であるため、全体として、1と同じ(p-1)*m奇数のsがあり、次のようになります。notnot

divisible n (n-1) = True
isPrime n = not (even n) && not (divisible n (n-1)) = True && not True = False

pが奇数の素数の場合、展開はに達しますdivisible p (p-1) = not^(p-3) (divisible p (p - (p-2)))。p-3である、でdivisible p 2あるeven p、であるFalse。

一般にdivisible n s、奇数を考慮し、が合成数の場合、またはが素数の場合、を超えない最大の約数とnします。の展開はまだ同じように進行しますdnsnd = 2ndivisible n s

divisible n s = not^k (divisible n (s-k))

除数が見つかりませんでしs-k > 2た。したがって、コンポジットの場合、次のようnになります。

divisible n s = not^(s-d) (divisible n d)
              = not^(s-d) (n `mod` d /= 0 && not (...))
              = not^(s-d) False
              = odd (s-d)
              = even s     -- since d is odd, as a divisor of an odd number

奇数の素数の場合n、

divisible n s = not^(s-2) (divisible n 2)
              = not^(s-2) (even n)
              = not^(s-2) False
              = odd s

したがって、または2の次に小さい除数までdivisible n sの距離のパリティを測定します。だったとき、開始点は常に偶数だったので、正しく機能しましたが、奇妙な場合があります。その場合、結果が反転し、コンポジットが素数と宣言され、その逆も同様です。snsn-1ceiling (sqrt (fromIntegral (n-1)))

最初の呼び出しが偶数の2番目の引数を取得することを確認すれば（したがって、奇数の場合はから開始）、divisible平方根がバインドされた奇数の素数性テストで関数を機能させることができますが、その関数のロジックは混乱しています。その名前はその結果を正しく説明していません。ceiling (sqrt (fromIntegral (n-1)))ceiling (sqrt (fromIntegral (n-1))) + 1

それを書くためのより慣用的な方法は

isPrime n = and [n `mod` k /= 0 | k <- [2 .. ceiling (sqrt $ fromIntegral n)]]

以前のテストで非除数であることがすでにわかっている除数の候補をスキップすると、テストはより効率的になります。2を除くすべての偶数をスキップするのは簡単です。

isPrime 2 = True
isPrime n = all ((/= 0) . (n `mod`)) (2 : [3, 5 .. ceiling (sqrt (fromIntegral n))])

少し複雑ですが、さらに効率的なのは3の倍数をスキップすることです

isPrime n = all ((/= 0) . (n `mod`)) (takeWhile (<= bound) (2:3:scanl (+) 5 (cycle [2,4])))
  where
    bound = ceiling (sqrt (fromIntegral (n-1)))

同じように、トライアル除数からより小さな素数の倍数を排除することができ、それぞれが少し効率を上げますが、より複雑なホイールを犠牲にして、たとえば5の倍数を排除すると

isPrime n = all ((/= 0) . (n `mod`)) (takeWhile (<= bound) (2:3:5: scanl (+) 7 (cycle [4,2,4,2,4,6,2,6])))
  where
    bound = ceiling (sqrt (fromIntegral (n-1)))
于 2012-06-13T16:47:46.920 に答える
2

これが私がそれを行う方法です： 

divisibleBy :: (Integral a) => a -> a -> Bool
divisibleBy x y = mod x y == 0

isPrime :: (Integral a) => a -> Bool
isPrime x = or $ map (divisibleBy x) [2..(x-1)]

divisibleBy割り切れるかどうかの簡単なテストです。isPrimeは、1 から x までのすべての整数に対してこのテストを実行しx、 がこれらの整数のいずれかで割り切れる場合に true を返します。コードで行ったように、上限を rootxに変更することもできますが、それ以外の場合は機能します。

于 2012-06-13T16:51:03.487 に答える