新・アルゴリズムとデータ構造入門 Java編6:高速な素数判定法

public class Main {
    // 整数を受け取り、素数かどうかを判定する関数
    static boolean primalityTest(long n) {
        
    }

    public static void main(String[] args) {
        long n = 813813813813L;
        boolean isPrime = primalityTest(n);
        if(isPrime){
            System.out.println(n + "は素数");
        }else{
            System.out.println(n + "は素数ではない");
        }
    }
}

public class Main {
    // 整数を受け取り、素数かどうかを判定する関数
    static boolean primalityTest(long n) {
        
    }

    public static void main(String[] args) {
        long n = 813813813813L;
        boolean isPrime = primalityTest(n);
        if(isPrime){
            System.out.println(n + "は素数");
        }else{
            System.out.println(n + "は素数ではない");
        }
    }
}

import java.util.Scanner;

public class Main {
    // 整数を受け取り、素数かどうかを判定する関数
    static boolean primalityTest(long n) {
        if (n == 1) {
            return false;
        }
        for (long i = 2; /* */ ; i++) {
            if (n % i == 0) {
                return false;
            }
        }
        return true;
    }

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

        long n = sc.nextLong();

        boolean isPrime = primalityTest(n);

        if (isPrime) {
            System.out.println("YES");
        } else {
            System.out.println("NO");
        }
    }
}

import java.util.Scanner;

public class Main {
    // 整数を受け取り、素数かどうかを判定する関数
    static boolean primalityTest(long n) {
        if (n == 1) {
            return false;
        }
        for (long i = 2; /* */ ; i++) {
            if (n % i == 0) {
                return false;
            }
        }
        return true;
    }

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

        long n = sc.nextLong();

        boolean isPrime = primalityTest(n);

        if (isPrime) {
            System.out.println("YES");
        } else {
            System.out.println("NO");
        }
    }
}

この動画を見るには

paiza会員登録のうえ

有料会員登録が必要です

演習1

問題ログインすると模範解答や入力を見ることができます

演習課題「素数判定をおこなう」

整数 n が入力として与えられるので、素数ならば YES と、素数ではないならば NO と出力してください。

右側のコードエリアには、入力を受け取って関数 primalityTest に渡し、その返り値によって YES と NO を出力するコードが用意されています。関数 primarityTest のコードを書き加え、問題を解くコードを完成させてください。

入力される値

2147483647

標準入力からの値取得方法はこちらをご確認ください

期待する出力値

YES

Tips

動画へ戻る

次のチャプターへ前のチャプターへ

※有料会員になるとこの動画をご利用いただけます

詳しい説明を読む

＃02:高速な素数判定法

このチャプターでは、高速な素数判定法について学習します。

条件式(Javaの場合)

整数 i が 2 以上 √n 以下であるということは、i^2 が 4 以上 n 以下であることと同値です。したがって、ループの条件式を以下のように書き換えてもよいです。この方法だと浮動小数点数がコードに登場しなくなるので、誤差について考慮する必要がなくなります。

for(long i = 2; i*i <= n; i++)

平方根の求め方(Javaの場合)

Math クラスの sqrt メソッドを用いると平方根を求めることができます。

double sqrtN = Math.sqrt(n)

プログラミング学習 > 新・アルゴリズムとデータ構造入門 Java編 > 新・アルゴリズムとデータ構造入門 Java編6: 素数 > 高速な素数判定法

ログインすると採点できます

コードの実行

有料会員になるとエンジニアに質問ができます

出力タイプ：

2147483647