Java 素数をチェックするプログラム（例付き）

素数とは何ですか?

素数とは、1より大きい自然数で、1と1自身以外では割り切れない数のことです。例えば、11は1と1自身以外では割り切れません。その他の素数は、2、3、5、7、11、13、17などであり、この数列は無限に続きます。

1より大きい素数でない数は、より小さな因数から構成されるため、合成数と呼ばれます。例えば、9は3で割り切れるので合成数であり、15は3と5で割り切れるので合成数です。

注意： 0と1は素数ではありません。2は唯一の偶数の素数であり、負の値は決して素数とはみなされません。

数が素数かどうかを確認する方法 Java

検証方法は、単純な割り算テストです。候補となる値を、より小さい整数で順番に割り算し、剰余演算子によって返される余りを調べます。余りがゼロであれば、約数が存在することが証明され、その数値は即座に不適格と判断されます。

プログラムロジック:

• 入力された数値（例えば17）を2から17までの値で割り、余りを調べます。余りが0であれば、その数値は素数ではありません。
• 半分以上で割り切れる数はありません。 したがって、私たちは次のことを行う必要があります ループ ただを通して numberToCheck/2入力が17の場合、半分は8.5となり、ループは2から8までの値を繰り返します。
• numberToCheck が別の数で完全に割り切れる場合、フラグ isPrime は次のように設定されます。 false そしてループは終了します。

ツー Java 特徴はアルゴリズム全体を担います。剰余演算子 % 整数除算の余りを返します。 break この文は答えがわかった時点でループを停止するため、不要な反復処理は実行されません。

Java 数が素数かどうかを判定するプログラム

以下のプログラムは、変数 numberToCheck に値 17 を代入し、除算の各ステップを逐一出力します。これにより、計算過程を一行ずつ確認できます。コードは編集可能なので、値を変更して、21 などの合成数で再度実行し、逆の結果を確認してみてください。

public class PrimenumberToCheckCheck {

 public static void main(String[] args) {
  int remainder;
  boolean isPrime=true;
  int numberToCheck=17; // Enter the number you want to check for prime

  //Loop to check whether the number is divisible by any number other than 1 and itself
  for(int i=2;i<=numberToCheck/2;i++)
  {
   //number is divided by i
            remainder=numberToCheck%i;
            System.out.println(numberToCheck+" Divided by "+ i + " gives a remainder "+remainder);

       //if remainder is 0 then the number is not prime and we break the loop. Else continue the loop
     if(remainder==0)
     {
        isPrime=false;
        break;
     }
  }
  // Check value true or false, if isPrime is true then the number is prime otherwise not prime
  if(isPrime)
     System.out.println(numberToCheck + " is a Prime number");
  else
     System.out.println(numberToCheck + " is not a Prime number");
    }
  }

期待される出力：

17 Divided by 2 gives a remainder 1
17 Divided by 3 gives a remainder 2
17 Divided by 4 gives a remainder 1
17 Divided by 5 gives a remainder 2
17 Divided by 6 gives a remainder 5
17 Divided by 7 gives a remainder 3
17 Divided by 8 gives a remainder 1
17 is a Prime number

17÷2は整数演算で8となるため、ループは8で停止します。余りがゼロになることは一度もないため、isPrimeフラグは初期値のtrueを維持し、最終条件で正の判定が出力されます。

平方根法を用いた最適化された素数判定

数の半分までを割り算するのは正しい方法ですが、無駄があります。数 n の約数が平方根より大きい場合、対応する約数は平方根より小さくなければならないため、既に発見されているはずです。したがって、√n までを割り算することで、はるかに少ない反復回数で同じ答えが得られます。

public class PrimeCheckOptimized {

    public static boolean isPrime(int n) {
        // 0, 1 and negative values are never prime
        if (n <= 1) {
            return false;
        }
        // 2 is the only even prime number
        if (n == 2) {
            return true;
        }
        if (n % 2 == 0) {
            return false;
        }
        // test only odd divisors up to the square root
        for (int i = 3; i * i <= n; i += 2) {
            if (n % i == 0) {
                return false;
            }
        }
        return true;
    }

    public static void main(String[] args) {
        int[] samples = {1, 2, 9, 17, 97};
        for (int value : samples) {
            System.out.println(value + " is prime: " + isPrime(value));
        }
    }
}

出力：

1 is prime: false
2 is prime: true
9 is prime: false
17 is prime: true
97 is prime: true

条件 i * i <= n Math.sqrt への浮動小数点演算呼び出しを回避し、ステップ値 2 によって偶数による約数をスキップします。例えば 1,000,003 のような値の場合、基本的なループでは約 500,000 回繰り返されますが、このバージョンでは 500 回未満で済みます。

ユーザーが入力した素数をチェックする

ハードコードされた入力はデモンストレーションには便利ですが、実際の演習では通常キーボード入力が求められます。Scannerクラスはコンソールから整数を読み込み、同じisPrimeメソッドに渡します。

import java.util.Scanner;

public class PrimeCheckUserInput {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        System.out.print("Enter a number: ");
        int number = sc.nextInt();

        boolean isPrime = number > 1;
        for (int i = 2; i * i <= number; i++) {
            if (number % i == 0) {
                isPrime = false;
                break;
            }
        }

        System.out.println(number + (isPrime ? " is a Prime number" : " is not a Prime number"));
        sc.close();
    }
}

サンプル実行例：

Enter a number: 29
29 is a Prime number

素数プログラムを作成する際によくある間違い

誤った提出物のほとんどは、メインループではなく境界値でエラーが発生します。以下に、初心者のコードで最もよく発生するエラーの一覧を示します。

1. ループを1から開始します。 すべての整数は1で割り切れるため、フラグはすぐにfalseに設定され、プログラムはどの数も素数ではないと報告します。
2. 1を素数として扱う： 値1は約数を1つしか持たないため、2つの約数の定義を満たさず、falseを返す必要があります。
3. break文を省略する： プログラムは正しい答えを返すものの、判定結果が判明した後も繰り返し処理を行うため、入力値が大きい場合に時間を浪費してしまう。
4. 使い方 i <= n 境界として： その数は常に自身を割り切るので、ループはnに到達する前に停止しなければならない。
5. との比較 = ==: 単一の等号は、値をテストするのではなく代入するため、if文の条件式でコンパイル時エラーが発生します。

素因数判定方法の比較

入力値のサイズと、単一の値をテストする必要があるか、範囲全体をテストする必要があるかに応じて、適切な方法を選択してください。

単一の値ではなく範囲全体を分類する必要がある場合は、ふるい分けの方がはるかに効率的です。 素数 Numbers 1から100へ このパターンを示しています。関連するループ駆動演習については、以下を参照してください。 フィボナッチ数列 Java Java 回文プログラム Bubbleソートアルゴリズム Java旗の宣言とカウンターについて復習が必要な初心者は、以下をお読みください。 Java variables 概して Java チュートリアル.

よくあるご質問