素数を求める / エラトステネスの篩 | アルゴリズム [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 <maxN; j += i) {
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のヘビーユーザーになので、「ここ」から会員登録してもらえるとサービス開発が捗ります!

📚 おすすめの書籍