Javaの素数を印刷

Question

このJavaコードは、2-100の間の素数を出力します。

これは問題なく動作します。

このコードは私によって行われていません。

しかし、私はこのコードで何が起こっているのか把握しようとしています。

2番目の（for）ループの後に何が起こっているか教えてもらえますか？

class primenumbers{ 
    public static void main(String args[]) 

    {  
     int i, j; 
     boolean isprime; 

     for(i=2; i < 100; i++) { 
      isprime = true; 

      // see if the number is evenly divisible 
      for(j=2; j <= i/j; j++) 
       // if it is, then its not prime 
       if((i%j) == 0) isprime = false; 

      if(isprime) 
       System.out.println(i + " is prime."); 
     } 
    } 
} 

Answer 1

だけ第二のループは、数は任意の他の数で割り切れる場合見つけようとする2から100

に番号を生成する第1のループ。ここでは、数値を一連の数値（2からprime_index）で除算しようとします。

数字が10であるとしましょう。最初の繰り返し（j = 2）のプライムインデックスは10/2 = 5です。つまり、数字10が2と5の間の任意の数で割り切れない場合、それは素数です。それは2によってそれ自身を非素数にすることで割り切れる。

数字が9であるとしましょう。ここで、素数インデックスは最初の繰り返し（j = 2）に対して9/2 = 4です。今、9 % 2はリマインダーとして1を与えます。したがって、ループは2番目の繰り返し（j = 3）に続きます。今度は素数インデックスは9/3 = 3（であることに注意してください。素数インデックス値は4から3に減らされます。）したがって、数値が3で割り切れない場合、素数として決定されます。

したがって、繰り返しごとに、プライムインデックスが減少し、反復回数が減少します。

Example for Number 97, 
j = 2, prime index = 97/2 = 48 (no of iterations for loop) 
j = 3, prime index = 97/3 = 32 (no of iterations for loop) 
j = 4, prime index = 97/4 = 24 (no of iterations for loop) 
j = 5, prime index = 97/5 = 19 (no of iterations for loop) 
j = 6, prime index = 97/6 = 16 (no of iterations for loop) 
j = 7, prime index = 97/7 = 13 (no of iterations for loop) 
j = 8, prime index = 97/8 = 12 (no of iterations for loop) 
j = 9, prime index = 97/9 = 10 (no of iterations for loop) 
j = 10, prime index = 97/10 = 9 (loop exits as condition failed 10 <= 9 and declares 97 as a prime number) 

は今、ここでのループは、実際に10回の反復の代わりの提案48回の反復を取りました。

コードを修正して理解を深めることにしましょう。

public static void main(String args[]) {  
     // Number from 2 to 100 
    for(int i=2; i < 100; i++) { 
     if (isPrimeNumber(i)) { 
      System.out.println(i + " is prime"); 
     } 
    } 
} 

ここでは、最適化されていない方法isPrimeNumberNotOptimized()を参照してください。

private static boolean isPrimeNumberNotOptimized(int i) { 
    for(int j=2; j <= i/2; j++) { 
     // if it is, then its not prime 
     if((i%j) == 0) { 
      return false; 
     } 
    } 
    return true; 
} 

また、プライムインデックスで最適化された別の方法isPrimeNumberOptimized()です。

private static boolean isPrimeNumberOptimized(int i) { 
    for(int j=2; j <= i/j; j++) { 
     // if it is, then its not prime 
     if((i%j) == 0) { 
      return false; 
     } 
    } 
    return true; 
} 

ここで、両方のメソッドが実行され、正しく素数が印刷されます。

しかし、最適化された方法では、97が10回目の繰り返しで素数であると判断されます。

そして、最適化されていない方法は、48回目の反復で同じものを決定します。

希望、あなたは今それを理解しています。

FYI：プライムインデックスは、計算に使用した数値です。数が割り切れない場合に派生プライム指数& 2の間に、その素数

Answer 2

外側（第1）ループは[2,100]のすべての数字を列挙する。

ループ内の（秒）ループは、最初のループの現在の数値が何かで割り切れるかどうかをチェックします。

このチェックは%（剰余）を使用して行われる：(i%j)==0j除算iの残りが0である場合。定義により、余りがゼロのときiはjで割り切れるので、素数ではない：isprime=false。

---

あなただけsqrt(i)（最後のセクションで説明）までチェックする必要がありますので、あなただけの[2,i/j]にチェックする必要があります。

は、内側ループのように書き換えることができると言った：

... 
int s = sqrt(i); 
for(j=2; j <= s; j++) 
... 

しかしsqrtしたがって、それはj^2 < iとj*j<iとj<i/j（両辺を二乗）としてj<=sqrt(i)を書き換える方が良いでしょう、分割よりも高価です。 jが十分大きい場合、j*jがオーバーフローする可能性があります。したがって、最終ステップで両側をjで分割します。

---

ここから取られたsqrt(i)の説明：Why do we check up to the square root of a prime number to determine if it is prime?

iが素数でない場合i = x * jように、その後、いくつかのxが存在します。 xとjの両方がsqrt(i)より大きい場合、x*jはiより大きくなります。

したがって、これらの因子（xまたはj）の少なくとも1つは、iの平方根以下でなければならず、iが素数であるかどうかをチェックするには、平方根。

Answer 3

これは、Eratosthenesの篩の改造です。

最初に、私はEratosthenesのふるいが何をしているかを要約します。あなたがすでにこれを知っていれば最後の段落にスキップすることができます。 Eratosthenesアルゴリズムのふるいは、特定の境界線を通ってループします。 （言ってください2 - 100）。それがループする回数ごとに、例えば2が素数（真）であり、2のすべての倍数が（偽である）ため、倍数が取り消されます。 3,5などと同じ。このアルゴリズムは所定の非素数ごとにスキップする。したがってアルゴリズムのシミュレーションは次のようになります。

2 ---prime number... cancels out 4, 6, 8, 10, 12.... 
3 ---prime number... cancels out 6, 9, 12, 15, 18... 
4 --- ALREADY CANCELLED OUT... Skip 
5 --- prime number... cancels out 10, 15, 20, 25... 
6 --- ALREADY CANCELLED OUT... Skip 

したがって、取り消されなかった数字は素数です。詳細については、こちらを参照してください。http://www.geeksforgeeks.org/sieve-of-eratosthenes/

ここで、あなたのアルゴリズムは数字のリストをループします。各数字（例えばx）について、（i/j）を通してループされた前の数字のどれかがxのファクタであるかどうかをチェックする。 i/jが2番目のforループの境界として使用される理由は効率のためです。 10（たとえば）が素数であるかどうかを調べている場合、6が要素であるかどうかを確認する必要はありません。便利にn /（n/2）で停止することができます。それが、その部分が達成しようとしていることです。