私の講師がここで何を得ているのか分かりません - Javaで素数を計算する講義ノート

Question

素数を計算するための単純なアルゴリズム が存在します。たとえば、 whileループを使用して、すべての正の整数iについてc％i ！= 0を確認することができます。 i> 1およびi < cです。

しかし、それははるかに良い 方法は、例えば、p- < Cそのすべての素数pに対して必ずそのCの％のP！= 0 を作っていることを確認するためにdicultない です。あなたのArrayListの素数を使って、 これは簡単です。もう一度 を入力すると、whileループを使用することが示唆されます。ループは です。

私はこれらのメソッドの両方を実装しようとしましたが、最初のものを取得しているうちに、c％i！= 0をチェックしていましたが、 c％p！= 0を使用する。これは、素数を計算するためにすべての素数を知る必要があるとは限りませんか？次のように私は、現時点で持っている何

は次のとおりです。

作品

public static void isPrime(int candidateNo) { 
while (i <= candidateNo/2) { 
    if (candidateNo%i==0 && i!=1) { 
    return false; 
    } 
    else 
    return true; 
} 

}

、はなはだ非効率的ですが。私は素数のarraylistを作成する関数を使用しています（関数がtrueを返す場合、数値はarraylistに追加されます）。

Answer 1

まあ、とにかくすべて素数のリストを作成しているので、数cが素数であるかどうかをチェックするとき、あなたはすでにあなたのリスト内のすべての小さい素数を持っています。右？ candidateNo/2よりも小さい任意の素数があなたの候補者を分割し​​た場合

ので、candidateNo/2よりも小さい代わりにテストのもしあれば数は、あなただけのテスト、あなたの候補者を分けます。

i = 2 to candidateNo/2から反復するのではなく、配列リストの要素を反復処理します。そのためには、この配列リストはisPrime関数からアクセスできるはずです。そのため、引数として渡すか、メインクラスのpublic static要素として渡してください。

Answer 2

素数でない任意の数は、素数要素に分解することができます。

例：

15 = 3 * 5 
24 = 2 * 2 * 2 * 3