問題タブ [primality-test]

コード：

このプログラムは、素数に関するフェルマーの定理に基づいています。N は素数としてテストされる数です。このプログラムは、'11' に対して正しい結果を表示していません。たぶん、私が特定していない何らかの間違いが原因です。

http://www.haskell.org/haskellwiki/Testing_primalityから、次のコードがあります。

primes は素数のリストです (おそらく無限)。

2 つの質問:

1. foldr関数に渡されたラムダをどのように読み取るか
2. 右から始まるのでfoldr、素数の無限リストが渡されたときにこの関数が機能するのはなぜですか? ラムダに短絡が組み込まれていると思いますか？

C++ で cplex コンサート テクノロジをコーディングしています。主問題 (主シンプレックス、双対シンプレックス、または内点を使用する場合、方法は重要ではありません) を解くとき、双対問題が無限の場合は双対変数の極値光線値、または双対変数の最適解値などの解の値を抽出できますか?双対問題には最適解がありますか?

Miller-Rabin 検定が 10¹⁸ までのすべての数について正しくなるには、どの証人のセットがあれば十分ですか? n < 341550071728321 の場合、証人として 17 までの素数を使用すれば十分であることを私は知っています。

素数かそうでないかを判断する述語を書きたいです。私はブルート フォース O(sqrt(n)) アルゴリズムによってこれを行っています。

1) number が 2 の場合、true を返し、それ以上述語をチェックしません。

2) 数が偶数の場合、false を返し、述語のチェックをこれ以上行いません。

3) 数が偶数でない場合は、平方根までの数の約数を確認します。プログラムのこの部分に到達すると、数は偶数ではないため、3 から始まる奇数の約数をチェックするだけでよいことに注意してください。偶数はステップ 2 で除去されました。

4) 偶数の約数が見つかった場合は、false を返し、それ以外は何もチェックしません。

5) チェックしている除数が数値の平方根より大きい場合は、true を返します。除数は見つかりませんでした。述語チェックを行わないようにします。

ここに私が持っているコードがあります:

しかし、私は問題に直面しています。たとえば、prime(1) をクエリするとします。プログラムはまだ除数をチェックしています。「！」を追加すると思いました 前の条件が true かどうかのチェックをプログラムが停止するようにします。プログラムがこれを行っている理由を誰か教えてもらえますか? 私はこれが初めてで、コードを単純化できることを知っていることに注意してください。ただし、ヒントをいただければ幸いです。

そのため、述語を 1 つだけ使用して、数値が素数かどうかを判断しようとしています。ここですべての数値が false と宣言されている理由がよくわかりません。

素数の場合は 1 を返し、合成数の場合は 0 を返す次のプログラムを作成しました。コンポジットを素数として誤って識別する可能性はありますが、次のアルゴリズムの時間の複雑さを改善 (減少) するための提案が必要です。