Javaの素数のテスト

Question

私のプログラムの目的は、ユーザーに整数を入力させるプログラムを書くことです。プログラムは整数を読み込み、それが素数であるかどうかを決定します。そしてそれがプライムでない場合、それはユーザーにすべての約数を伝えます。

これは私が持っているところまでですが、私が169や289のような数字でテストしたとき、プログラムは素数であると言っていました。私はこの問題は、この行の上に横たわっていることを理解する：

int[] div = new int[] { 2,3,4,5,6,7,8,9}; 

が、私はこのような何かをしようとした：

for (int s = nr; s != 0 ; s--) { 
     if (nr%s == 0) { 
     int[] div = new int[]{s}; } 

は、しかし、それは動作しませんでした。ちょっとした助けや正しい方向が大いに役立ちます。ありがとうございました！

public static void main(String[] args){ 
    System.out.println("enter a number:"); 
    Scanner scanner = new Scanner (System.in); 
    int nr = scanner.nextInt(); 
    int[] div = new int[] { 2,3,4,5,6,7,8,9}; 
    boolean prime = nr >= 2; 
    int i = nr; 
    for(int j = 0; j< div.length && prime && i> div[j]; j++) 
     if(i % div[j] == 0) 
      prime = false; 

    if(prime){ 
     System.out.println(i + " is a prime"); 
    }else{ 
     System.out.print(i + " is divisible"); 
     for(int k = 2; k < i; k++) 
      if(i % k == 0){ 
       System.out.print(k); 
       System.out.print(",");} 

       } 

      } } 

Answer 1

除数には9までの数字しか試していません。だから、10以上の要因を持つもの、169は13で13であるなど、13を見つけることはできません。

除数を配列に格納する代わりに、整数を使用して上向きにカウントすることを検討してください。つまり、div[j]の代わりにjを除数として使用し、10で停止させないでください。できるだけ多くの除数で停止させてください（これは、素数を見つけようとしている数字の平方根です）の）。

Answer 2

169を小数点として扱う理由は、2〜9の値で除算し169を13乗しているため、2〜9の任意の数値で割り切れないためです。

このメソッドhttp://en.wikipedia.org/wiki/Sieve_of_Eratosthenesを使用すると、1とnの間のすべての素数を見つけて、それを使って自分の番号が素数であるかどうかを判断できます。

Answer 3

数が素数である。この場合で見つけることは非常に簡単で、基本的な方法：

は2とn^1月2日までの間の各数でn個の分割を続行します。それらのうちのいずれかが均等に分かれている場合、あなたが要素を見つけたので、nは素数ではありません。 nに平方根よりも小さい因子がない場合、nは素数です。 n = a * bの場合、aとbの両方がnの平方根を超えることはできないので、n^1/2以下の除数だけを調べれば十分です。

for(int i=2;i<=n^1/2;i++) 
    { 
    if(num%i)==0 //number not prime 
    else continue; 
    } 

    if none of the if statements in the loop were true, number is prime 

Answer 4

ただ、しかし確実性パラメータを使用する方法がない100％を確認してください...ジャワに組み込まれBigInteger.isProbablePrime()ライブラリ関数を使用します。

BigInteger.valueOf(13).isProbablePrime(10000) 

Answer 5

<edit> I should have looked a little closer... I guess it IS homework, so this answer is not really any good to you, eh? Well, I'm gonna leave it up in case the information here becomes useful to someone somewhere... </edit>

あなたが実際に（これは宿題ではない場合、つまり）の計算を自分で行う必要がない場合は、常にJavaのBigIntegerのクラスを使用することを選ぶことができます。たとえば：

生活の中でほとんどの事と同じように

public class Prime { 
    public static void main(String[] args){ 
     long start = System.nanoTime(); 
     System.out.println("enter a number:"); 
     Scanner scanner = new Scanner(System.in); 
     BigInteger bigInt = scanner.nextBigInteger(); 
     boolean prime = bigInt.isProbablePrime(10); 
     System.out.println(prime); 
    } 
} 

、少なくともカップルの注意点があります

1. 数の素数を報告する確率は100％ではない、またそれは（することができますが私たちはそれについて一瞬で話します）。

2. より正確にテストしたい場合は、時間がかかります。

これはOracle's Official Documentationで詳細です：

isProbablePrime

public boolean isProbablePrime (int certainty)

返しtrueそれは必ず合成場合はこのBigIntegerがfalse、おそらく素数である場合。 certaintyが<= 0の場合、trueが返されます。

パラメータ：

certainty - 呼び出し側が許容しない不確実性の尺度：コールはこのBigIntegerが素数で(1 - 1/(2^certainty))を超えていることtrue確率を返します。このメソッドの実行時間は、このパラメータの値に比例します。

戻り値：

trueこのBigIntegerはおそらく素数である場合、falseそれは必ず合成場合。

非常に正確な素数テストにはどのくらい時間がかかるのか不思議に思ったので、簡単なベンチマークを行い、いくつかの数字を実行しました。

1から50までの各確信度に対して百万未満のすべての奇数の素数を計算しました（0以下は常に真を返します）。

時間はミリ秒単位です（ただし、時刻はSystem.nanoTime()を呼び出して取得してから、最も近いミリ秒に丸めます）。ここで

私の結果は次のとおりです。

Certainty  Time(ms)  Chance of Correctness 
1    1417   50.0% 
2    932    75.0% 
3    1064   87.5% 
4    1063   93.75% 
5    1183   96.875% 
6    1195   98.4375% 
7    1313   99.21875% 
8    1308   99.609375% 
9    1441   99.8046875% 
10    1443   99.90234375% 
11    1567   99.951171875% 
12    1571   99.9755859375% 
13    1690   99.98779296875% 
14    1691   99.993896484375% 
15    1817   99.9969482421875% 
16    1822   99.99847412109375% 
17    1944   99.99923706054688% 
18    1941   99.99961853027344% 
19    2069   99.99980926513672% 
20    2073   99.99990463256836% 
21    2197   99.99995231628418% 
22    2200   99.99997615814209% 
23    2324   99.99998807907104% 
24    2340   99.99999403953552% 
25    2453   99.99999701976776% 
26    2465   99.99999850988388% 
27    2647   99.99999925494194% 
28    2626   99.99999962747097% 
29    2715   99.99999981373549% 
30    2710   99.99999990686774% 
31    2844   99.99999995343387% 
32    2818   99.99999997671694% 
33    2950   99.99999998835847% 
34    3074   99.99999999417923% 
35    3121   99.99999999708962% 
36    3167   99.99999999854481% 
37    3295   99.9999999992724% 
38    3302   99.9999999996362% 
39    3334   99.9999999998181% 
40    3360   99.99999999990905% 
41    3493   99.99999999995453% 
42    3583   99.99999999997726% 
43    3663   99.99999999998863% 
44    3599   99.99999999999432% 
45    3783   99.99999999999716% 
46    3816   99.99999999999858% 
47    3964   99.99999999999929% 
48    3898   99.99999999999964% 
49    4029   99.99999999999982% 
50    3969   99.99999999999991% 
total: 124312 

あなた500,000数字の素数を評価し、でも私は、試験した最高確信値で、見ることができるようにわずか4秒かかりましたし、各評価は99.99999999999991%のチャンスがありました

したがって、意図したアプリケーションのパフォーマンスが非常に重要でない場合は、25のような（比較的）高い数値を使用できます。アルゴリズムは、時間の99.99999701976776秒の素数として正しく数を報告します。あなたがロケット科学者であればお勧めできません。そしてが、ロケット科学者なら、あなたはあなたのソリューションを他の場所に見つけることを願っています:)。