新・アルゴリズムとデータ構造入門 Java編6:エラトステネスの篩

import java.util.Arrays;

public class Main {
    static boolean[] eratosthenes(int n) {
    }

    public static void main(String[] args) {
        int n = 813;
        boolean[] isPrime = eratosthenes(n);
        for(int i = 1; i <= n; i++){
            if(isPrime[i]){
                System.out.println(i + "は素数");
            }else{
                System.out.println(i + "は素数ではない");
            }
        }
    }
}

import java.util.Arrays;

public class Main {
    static boolean[] eratosthenes(int n) {
    }

    public static void main(String[] args) {
        int n = 813;
        boolean[] isPrime = eratosthenes(n);
        for(int i = 1; i <= n; i++){
            if(isPrime[i]){
                System.out.println(i + "は素数");
            }else{
                System.out.println(i + "は素数ではない");
            }
        }
    }
}

import java.util.Arrays;

public class Main {
    static boolean[] eratosthenes(int n) {
        boolean isPrime[] = new boolean[n + 1];
        Arrays.fill(isPrime, true);
        isPrime[0] = isPrime[1] = false;

        for (int i = 2; i <= n; i++) {
            if (!isPrime[i]){
                continue;
            }
            for (int j = /* */) {
                isPrime[j] = false;
            }
        }
        return isPrime;
    }

    public static void main(String[] args) {
        boolean[] isPrime = eratosthenes(1000);
        
        for(int i = 1; i <= 1000; i++){
            System.out.print(i + " : ");
            if(isPrime[i]){
                System.out.println("prime");
            }else{
                System.out.println("not prime");
            }
        }
    }
}

import java.util.Arrays;

public class Main {
    static boolean[] eratosthenes(int n) {
        boolean isPrime[] = new boolean[n + 1];
        Arrays.fill(isPrime, true);
        isPrime[0] = isPrime[1] = false;

        for (int i = 2; i <= n; i++) {
            if (!isPrime[i]){
                continue;
            }
            for (int j = /* */) {
                isPrime[j] = false;
            }
        }
        return isPrime;
    }

    public static void main(String[] args) {
        boolean[] isPrime = eratosthenes(1000);
        
        for(int i = 1; i <= 1000; i++){
            System.out.print(i + " : ");
            if(isPrime[i]){
                System.out.println("prime");
            }else{
                System.out.println("not prime");
            }
        }
    }
}

この動画を見るには

paiza会員登録のうえ

有料会員登録が必要です

演習1

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

演習課題「エラトステネスの篩を実装する」

右側のコードエリアには、関数 eratosthenes を用いて 1 以上 1,000 以下の全ての整数について素数判定をおこなうコードが用意されています。関数 eratosthenes のコードを書き加え、コードを完成させてください。

入力される値

なし

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

期待する出力値

なし

Tips

動画へ戻る

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

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

詳しい説明を読む

＃03:エラトステネスの篩

このチャプターでは、ある整数以下のすべての素数を見つけるアルゴリズムである「エラトステネスの篩」について学習します。

ループ範囲(Javaの場合)

isPrime を計算するときの i のループ範囲は、実は √n までで十分です。


boolean isPrime[] = new boolean[n + 1];
Arrays.fill(isPrime, true);
isPrime[0] = isPrime[1] = false;

for (int i = 2; i <= Math.sqrt(n); i++) {
    if (!isPrime[i]){
        continue;
    }
    for (int j = i + i; j <= n; j += i) {
        isPrime[j] = false;
    }
}

プログラミング学習 > 新・アルゴリズムとデータ構造入門 Java編 > 新・アルゴリズムとデータ構造入門 Java編6: 素数 > エラトステネスの篩

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

コードの実行

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

出力タイプ：

なし