9

以下のコード スニペットは、指定された数値が素数であるかどうかを確認します。なぜこれが機能するのか、誰かが私に説明できますか? このコードは、Java 試験のために提供されたスタディ ガイドに記載されていました。

public static void main(String[] args)
{    
    int j = 2;
    int result = 0;
    int number = 0;
    Scanner reader = new Scanner(System.in);
    System.out.println("Please enter a number: ");
    number = reader.nextInt();
    while (j <= number / 2)
    {
        if (number % j == 0)
        {
           result = 1;
        }
        j++;
    }
    if (result == 1)
    {
        System.out.println("Number: " + number + " is Not Prime.");
    }
    else
    {
        System.out.println("Number: " + number + " is Prime. ");
    }
}
4

5 に答える 5

25

全体的な理論

条件は、が正確に割り切れるif (number % j == 0)かどうかを尋ねます。numberj

素数の定義は

その数と 1 だけで割り切れる数

したがって、2 と数値の間のすべての数値をテストし、それらのいずれも正確に割り切れない場合、それは素数であり、そうでない場合は素数ではありません。

もちろん、実際に まで行く必要はありnumberませnumberんnumber。

特定のセクション

ループ中

このセクションは、増加する j の値を通過します。number= 12 と仮定すると、 j= 2,3,4,5,6を通過します。

  int j = 2;
  .....
  while (j <= number / 2)
  {
      ........
      j++;
  }

If ステートメント

が で正確に割り切れるresult場合、このセクションは 1 に設定されます。1 に設定されると、0 にリセットされることはありません。numberjresult

  ......
  if (number % j == 0)
  {
     result = 1;
  }
  .....

さらなる改善

もちろん、実際にはこれよりも高くする必要はないため、さらに改善することもできますがsqrt(number)、このスニペットではそれを行わないことにしました。高くする必要がない理由は、(たとえば) 40 が 4 で正確に割り切れる場合は 4*10 であり、4 と 10 の両方をテストする必要がないためですsqrt(number)。

resultまた、ブール値として使用することを意図しているように見えますが、実際には整数 0 と 1 を使用して true と false を表していることにも注意してください。これは良い習慣ではありません。

于 2013-10-22T10:05:44.817 に答える
7

進行中のプロセスを説明するために各行にコメントを付けてみました。

int j = 2;   //variable
int result = 0; //variable
int number = 0; //variable
Scanner reader = new Scanner(System.in); //Scanner object
System.out.println("Please enter a number: "); //Instruction
number = reader.nextInt(); //Get the number entered
while (j <= number / 2) //start loop, during loop j will become each number between 2 and 
{                             //the entered number divided by 2
    if (number % j == 0) //If their is no remainder from your number divided by j...
    {
        result = 1;  //Then result is set to 1 as the number divides equally by another number, hergo
    }                //it is not a prime number
    j++;  //Increment j to the next number to test against the number you entered
}
if (result == 1)  //check the result from the loop
{
    System.out.println("Number: " + number + " is Not Prime."); //If result 1 then a prime   
}
else
{
    System.out.println("Number: " + number + " is Prime. "); //If result is not 1 it's not a prime
}
于 2013-10-22T10:11:15.320 に答える
2

Java java.math.BigInteger クラスには、数値の素数をチェックするメソッドisProbablePrime(int 確かさ)が含まれています。

isProbablePrime(int certainty):BigInteger指定された数値が素数かどうかをチェックするクラス内のメソッド。の場合、が素数certainty = 1の場合は true を返し、が複合の場合は false を返します。BigIntegerBigInteger

この方法では、Miller-Rabin primality アルゴリズムを使用して素数性をチェックします。

import java.math.BigInteger;

public class TestPrime {

    public static void main(String[] args) {
        int number = 83;
        boolean isPrime = testPrime(number);
        System.out.println(number + " is prime : " + isPrime);

    }

    /**
     * method to test primality
     * @param number
     * @return boolean
     */
    private static boolean testPrime(int number) {
        BigInteger bValue = BigInteger.valueOf(number);

        /**
         * isProbablePrime method used to check primality. 
         * */
        boolean result = bValue.isProbablePrime(1);

        return result;
    }
}

Output: 83 is prime : true

詳細については、私のブログを参照してください。

于 2016-05-04T05:03:54.323 に答える