ガガーリンの言葉として知られる「地球は青かった」は、1961年4月13日付けのイズベスチヤに掲載されたルポ（着陸地点にいたオストロウーモフ（Георгий ОСТРОУМОВ）記者によるもの）によれば、原文では "Небо очень и очень темное , а Земля голубоватая . " となっており、日本語では、「空は非常に暗かった。一方、地球は青みがかっていた」となる。朝日新聞4月13日夕刊、毎日新聞4月13日夕刊、読売新聞4月13日朝刊は、この記事を基にしてガガーリンの言葉を伝えている。
エラトステネスはどうやって地球の大きさを知ったのか – 2000年前とは思えぬ脅威の精度 | 数学の面白いこと・役に立つことをまとめたサイト
⇧ 「地球は青かった」ってことは言ってなかったと...、2020年を迎え順調な正月太りを達成した、どうも、ボクです。
そんな地球ですが、
紀元前240年（約2000年前）、ギリシャの天文学者エラトステネスは、地球の大きさをはじめて測量した人物として知られています。
エラトステネスはどうやって地球の大きさを知ったのか – 2000年前とは思えぬ脅威の精度 | 数学の面白いこと・役に立つことをまとめたサイト
⇧ 2000年前に測量されてたと！
ちなみに、正確な地球の半径は、6371kmです。その差は、 6371–6263=108 km であり、わずか1.7%の誤差しかありません。 約2000前の測量技術を考えるとこの誤差の小ささは驚異的といっていいでしょう。
エラトステネスはどうやって地球の大きさを知ったのか – 2000年前とは思えぬ脅威の精度 | 数学の面白いこと・役に立つことをまとめたサイト
⇧ エラトステネスさん、精度が高いっす！
今回は、そんな、エラトステネスさんが考案した「エラトステネスの篩」について調査してみました。
エラトステネスの篩って？
素数判定で、高速化って調べると、だいだい検索に出てくるやつです。
エラトステネスの篩 (エラトステネスのふるい、英: Sieve of Eratosthenes) は、指定された整数以下の全ての素数を発見するための単純なアルゴリズムである。古代ギリシアの科学者、エラトステネスが考案したとされるため、この名がある。
⇧ 古代ギリシアで生まれた方法らしい。
- 一般的な数に対する判定法
- 特殊な条件の数に対する判定法
- Pocklingtonの判定法 - N = FR+1, F> sqrt(N), Fの素因数分解が既知の場合の判定法
- リュカ・テスト - pが(4j + 3)型素数のメルセンヌ数に対する判定法
- リュカ–レーマー・テスト - p が奇素数のメルセンヌ数に対する判定法
- リュカ–レーマー–リーゼル・テスト
- 特殊な形の数に対する判定法
⇧ 「エラトステネスの篩」は載っていると...というか「素数判定」の種類が多いな...。
高速化しないといけない時もありますと
素数判定のアルゴリズムのサンプルでJavaのものってなかなか見つからないんですが、
⇧ ってあったんで、参考に実装してみたのですが、
⇧ Aizu Online Judgeの問題で、制限時間オーバーになってしまった...
ちなみに、タイムオーバーになったコーディング。
package main;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
public static void main(String[] args) throws NumberFormatException, IOException {
// TODO 自動生成されたメソッド・スタブ
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
int primaryRange = Integer.valueOf(in.readLine());
int[] primaryCount = new int[primaryRange];
int result = 0;
for (int index = 0; index < primaryRange; index++) {
primaryCount[index] += primaryNumber(Integer.valueOf(in.readLine()));
}
for (int count: primaryCount) {
result += count;
}
System.out.println(result);
}
public static int primaryNumber(int target) {
int count = 0;
boolean isPrime = false;
if (target == 2) {
return ++count;
} else if (target % 2 == 0) {
return count;
}
if (target == 3) {
return ++count;
}
for (int index = 3; index < target; index += 2) {
if (target % index == 0) {
return count;
}
}
isPrime = true;
if (isPrime) {
++count; // 素数をカウント
}
return count;
}
}
⇧ 配列とかで時間かかってるのかな？よく分からんですが、処理が遅いと。
10000個の整数を、素数判定した場合、0.311s かかっていますと。
エラトステネスの篩で実装してみる
素数判定を速くするしかないんですが、ネットで調べると、「エラトステネスの篩」ぐらいしかヒットしないんですよね...
しかも、結構、「試し割り」を「エラトステネスの篩」と思って実装してる人も多いみたいです。
⇧ 上記サイト様は、「エラトステネスの篩」を実装してくださっているようなので、参考にさせていただきました。
0.011s になりました～！
コーディングはこんな感じ。
package main;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
public static void main(String[] args) throws NumberFormatException, IOException {
// TODO 自動生成されたメソッド・スタブ
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
int primaryRange = Integer.valueOf(in.readLine());
int result = 0;
for (int index = 0; index < primaryRange; index++) {
result += primaryNumber(Integer.valueOf(in.readLine()));
}
System.out.println(result);
}
public static int primaryNumber(int target) {
int count = 0;
boolean isPrime = true;
int sqrt = (int)Math.sqrt(target);
for (int i = 2; i <= sqrt; i++) {
if (target % i == 0) {
isPrime = false;
break;
}
}
if (isPrime) {
++count;
}
return count;
}
}
⇧ sqrt は平方根らしいですが、なんで平方根でイケるのかとかは、
szarny.hatenablog.com⇧ 上記サイト様が詳しいです。
まぁ、素数の研究に対する賞金がスゴイな～。
今回見つかった素数は2325万桁台ですけど、1億桁の素数を最初に見つけた人類には、電子フロンティア財団（EFF）から15万ドル（約1666万円）の賞金が贈られますよ。グッドラック！
⇧ 数学の知識が欲しいな～。
今回もモヤモヤ感が半端ないですが、「エラトステネスの篩」は結構速いらしいということが分かったということで。
今回はこのへんで。
