競技プログラミング

1〜Nの素数を出力するプログラム Python Java Kotlin

素数の出力

この記事で解決できる問題

  • 素数の一覧を出力したい
  • エラトステネスのふるいを実装したい
  • コピペで使えるコードが欲しい

この記事では競技プログラミングで使用できる、素数の出力プログラムを紹介します。
対応するプログラミング言語は、Python、Java、Kotlin です。

この記事では、エラトステネスのふるいというアルゴリズムを使った素数の出力プログラムを公開しています!
実際に検証として 1,000,000 までの素数を出力してみて、想定通りの出力であることを確認しました。

記事の前半ではコピペで使えるプログラムを、後半では主にアルゴリズムの解説をしています。
最後にソースコードの処理手順の解説をまとめたので、ぜひ最後まで読んでみてくださいね!

素数出力プログラム

Python

import math

def generate_primes(max):
    prime_list = []

    if max < 2:
        return prime_list
    
    # ステップ1 探索リストに2からxまでの整数を昇順で入れる
    search_list = range(2, max + 1)

    sqrt_max = math.floor(math.sqrt(max))
    while True:
        # ステップ2 探索リストの先頭の数を素数リストに移動し、その倍数を探索リストから篩い落とす
        prime = search_list[0]
        # 素数リストに追加
        prime_list.append(prime)
        # 倍数をふるい落とす
        search_list = [n for n in search_list if n % prime != 0]

        # ステップ3 上記の篩い落とし操作を探索リストの先頭値がxの平方根に達するまで行う
        if prime >= sqrt_max:
            break
    
    # ステップ4 探索リストに残った数を素数リストに移動して処理終了。
    prime_list.extend(search_list)

    return prime_list

Java

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.stream.Collectors;
import java.util.stream.LongStream;

public static List<Long> generatePrimes(long max) {
    List<Long> primeList = new ArrayList<>();

    if (max < 2) {
        return primeList;
    }

    // ■ ステップ1 探索リストに2からxまでの整数を昇順で入れる。
    List<Long> searchList = new LinkedList<>(
            LongStream.range(2, max + 1)
                    .boxed()
                    .collect(Collectors.toList())
    );

    long sqrtMax = (long) Math.sqrt(max);
    while (true) {
        // ■ ステップ2 探索リストの先頭の数を素数リストに移動し、その倍数を探索リストから篩い落とす。
        long prime = searchList.get(0);
        // 素数リストに追加
        primeList.add(prime);
        // 倍数をふるい落とす
        searchList.removeIf(n -> n % prime == 0);

        // ■ ステップ3 上記の篩い落とし操作を探索リストの先頭値がxの平方根に達するまで行う。
        if (prime >= sqrtMax) break;
    }

    // ■ ステップ4 探索リストに残った数を素数リストに移動して処理終了。
    primeList.addAll(searchList);

    return primeList;
}

Kotlin

import kotlin.math.sqrt

fun generatePrimes(max: Long): List<Long> {
    val primeList = mutableListOf<Long>()
    if (max < 2) {
        return primeList
    }

    val searchList = LongRange(2, max).toMutableList()
    val sqrtMax = sqrt(max.toDouble()).toLong()
    do {
        val prime = searchList[0]
        primeList.add(prime)

        searchList.removeIf { it % prime == 0L }
    } while (prime < sqrtMax)

    primeList.addAll(searchList)
    return primeList
}

アルゴリズム解説

このコードは、エラトステネスのふるいというアルゴリズムを実装しています。
エラトステネスのふるいについての詳細は以下のリンクに記載があります。

エラトステネスの篩(Wikipedia)

ゴイチ

エラトステネスという名前の響きには、なぜかワクワクした感情を覚えますね(笑

Wikipedia には、エラトステネスのふるいを図解したアニメーションgifが載っていましたので、以下引用します。

エラトステネスのふるいの図解

エラトステネスのふるい
ドイツ語版ウィキペディアのSKoppさん - 投稿者自身による作品transferred from German Wikipedia, original file was located at de:Bild:Animation Sieb des Eratosthenes.gif, CC 表示-継承 3.0, https://commons.wikimedia.org/w/index.php?curid=327783による

ここがポイント

このアニメーションでは、例として120までの素数を求めています。
アルゴリズムの基本的な考えは、2√x までの素数の倍数をすべてつぶすと、残った数が必然的に素数になる というものです。
これを実装することで、比較的高速に素数の一覧を求めることができます。

実際に動かしてみる

public static void main(String[] args) {
    System.out.println(generatePrimes(1).toString());
    System.out.println(generatePrimes(2).toString());
    System.out.println(generatePrimes(3).toString());
    System.out.println(generatePrimes(13).toString());
    System.out.println(generatePrimes(120).toString());
    // https://ja.wikipedia.org/wiki/%E7%B4%A0%E6%95%B0%E3%81%AE%E4%B8%80%E8%A6%A7

    System.out.println("100万までの素数の数は 78498 = " + generatePrimes(1000000).size());
    // https://www.usamimi.info/~geko/arch_acade/elf009_prime/list100.html
}

出力結果

[]
[2]
[2, 3]
[2, 3, 5, 7, 11, 13]
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113]
100万までの素数の数は 78498 = 78498

出力結果は期待通りになっています。100万件の処理時間は私のMac Bookで数秒でした。

まとめ

エラトステネスのふるいで素数を出力するには以下の手順を実施します。

素数の出力手順

  • 2 から x までの整数を昇順で探索リストに格納する。
  • 探索リストの先頭の数を素数リストに移動し、その倍数を探索リストから篩い落とす。
  • 篩い落とし操作を探索リストの先頭値が √x に達するまで行う。
  • 最後まで探索リストに残った数を素数リストに追加する。

以上の手順をプログラムで表現すれば、x までの素数の出力をすることが出来ます。
比較的単純で効果の高いアルゴリズムだと思います。

ゴイチ

エラトステネスさんという人が考えたアルゴリズムなので、エラトステネスのふるいと言うそうですよ。

競技プログラミングなどで素数を出力する機会があれば使ってみて下さいね!

(注)この記事はQiitaに投稿した過去の記事を再構成したものです

この記事は役に立ちましたか?

  • この記事を書いた人
アバター画像

ゴイチ

ソフトウェアエンジニア歴20年。 C/C++、Java、C#、Kotlinが得意で、組込系からAndroidアプリ、大規模なWebサービスなど幅広いプログラミング経験があります。 現在は某SNSの会社でWebエンジニアをしています。

-競技プログラミング
-, , , , ,