Javaの解答例：学習記録：A26 - Prime Check , 競技プログラミングの鉄則 演習問題集

はじめに

競技プログラミングの鉄則　演習問題集の「A26 - Prime Check 」という問題です！

今回のポイント

ポイントは素数かどうかを判定するときに、整数の性質を使うのがポイントです！素数とは1とその数以外の約数を持たない数の事でしたよね。逆に言えば、普通の約数を持つ場合は、素数ではないということ。

18が素数かどうかを判定したいとします。平方根を取ってあげるといい。素数じゃないときは、平方根以下の約数が絶対に存在するから。18の平方根は9。他の数でもやってみてください。素数と素数じゃないバージョン両方試すと分かりやすいかと。

目次

問題と解説へのリンク

問題

atcoder.jp

解説

github.com

解答例

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int q = sc.nextInt();
        int[] list = new int[q];

        for (int i = 0; i < q; i++) {
            list[i] = sc.nextInt();
        }

        for (int i = 0; i < q; i++) {
// 下記にisPrime() という関数を作成している
            if (isPrime(list[i])) {
                System.out.println("Yes");
            } else {
                System.out.println("No");
            }
        }
    }

    private static boolean isPrime (int x) {
// 2以上っていうのがみそ
// 平方根を　i * i　で表している
        for (int i = 2; i * i <= x; i++) {
            if (x % i == 0) {
                return false;   
            }
        }

        return true;
    }
}