素数を求める / エラトステネスの篩 | アルゴリズム [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.InputStreamReader;
import java.util.Arrays;
public class Main {
private static final int maxNumber = 1_000_000;
public static void main(String[] args) throws Exception {
int[] primeNumberCount = calcPrimeNumberCount();
BufferedReader r = new BufferedReader(new InputStreamReader(System.in));
int num;
String str;
while((str = r.readLine()) != null) {
num = Integer.parseInt(str);
System.out.println(primeNumberCount[num]);
}
}
private static int[] calcPrimeNumberCount() {
boolean[] isPrime = new boolean[maxNumber];
Arrays.fill(isPrime, true);
isPrime[0] = false;
isPrime[1] = false;
int sqrtMaxNum = (int) Math.floor(Math.sqrt(maxNumber));
for (int i = 2; i < sqrtMaxNum; i++) {
for (int j = i*i; j < maxNumber; j += i) {
if (!isPrime[j]) { continue; }
isPrime[j] = false;
}
}
int count = 0;
int[] primeCount = new int[maxNumber];
for (int i = 0; i < maxNumber; i++) {
if (isPrime[i]) {
count ++;
}
primeCount[i] = count;
}
return primeCount;
}
}

🚜 GitHubリポジトリ

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

morizyun/aoj-ruby-python - GitHub

📚 おすすめの書籍