素数を求める / エラトステネスの篩 | アルゴリズム [AOJ 0009][Ruby/Python/Java]

素数の数を求めるAOJの「Prime Number - Aizu Online Judge」のRuby / Python / Javaでのサンプル回答です。

『エラトステネスの篩 - Wikipedia』
という有名な素数を求めるアルゴリズムを使っています。

😎 エラトステネスの篩(ふるい)

概要

エラトステネスの篩 - Wikipedia

AOJ問題

Prime Number - Aizu Online Judge

Aizu Online Judgeの6桁次の素数を求める問題。

Rubyコード

n = 1000000

# エラトステネスの篩
# 指定された整数以下の全ての素数を見つける
ns = (n**0.5).to_i + 1
is_prime = [false, false] + [true]*(n-1)
2.upto(ns) do |i|
  next if !is_prime[i]
  (i*i).step(n, i) do |j|
    is_prime[j] = false
  end
end

count = 0
list = (0..n).map do |i|
  count += 1 if is_prime[i]
  count
end

while gets
  puts list[$_.to_i]
end

Pythonコード

from bisect import bisect

n = 1000000
sn = int(n**0.5)+1

num = [False, False] + [True]*(n-1)
for i in xrange(2, int(n**0.5)+1):
  if num[i]:
    for j in xrange(i**2, n, i):
      num[j] = False
prime = [i for i in xrange(2, n) if num[i]]

while True:
  try:
    print bisect(prime, input())
  except:
    break

Javaコード

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    int[] primeCountList = calcPrimeNumber();

    while (true) {
      String tmp = br.readLine();
      if (tmp == null) {
        break;
      }
      int num = Integer.valueOf(tmp);
      System.out.println(primeCountList[num]);
    }
  }

  private static int[] calcPrimeNumber() {
    int maxN = 1_000_000;
    int sqrtN = (int) Math.sqrt(maxN);

    boolean[] isPrimeList = new boolean[maxN];
    for (int i = 2; i < maxN; i++) {
      isPrimeList[i] = true;
    }

    for(int i = 2; i < sqrtN + 1; i++) {
      if (!isPrimeList[i]) {
        continue;
      }
      for (int j = i*i; j         isPrimeList[j] = false;      }    }    int[] primeCountList = new int[maxN];    int count = 0;    for (int i = 2; i < maxN; i++) {      if (isPrimeList[i]) {        count++;      }      primeCountList[i] = count;    }    return primeCountList;  }}
        isPrimeList[j] = false;
      }
    }

    int[] primeCountList = new int[maxN];
    int count = 0;
    for (int i = 2; i < maxN; i++) {
      if (isPrimeList[i]) {
        count++;
      }
      primeCountList[i] = count;
    }

    return primeCountList;
  }
}

🍮 GitHubリポジトリ

当面はAOJを解きながら、アルゴリズムの再勉強をしていくつもりです。
Ruby/Python/JavaでのAOJの回答は下のリポジトリに保存しておきます。もしツッコミとかあればぜひ＾＾

morizyun/aoj-ruby-python - GitHub

🖥 VULTRおすすめ

「VULTR」はVPSサーバのサービスです。日本にリージョンがあり、最安は512MBで2.5ドル/月($0.004/時間)で借りることができます。4GBメモリでも月20ドルです。 最近はVULTRのヘビーユーザーになので、「ここ」から会員登録してもらえるとサービス開発が捗ります！

📚 おすすめの書籍