素数判定のエラトステネスの篩はどれぐらい速いんすかね?

f:id:ts0818:20200103172959j:plain

ガガーリンの言葉として知られる「地球は青かった」は、1961年4月13日付けのイズベスチヤに掲載されたルポ(着陸地点にいたオストロウーモフ(Георгий ОСТРОУМОВ)記者によるもの)によれば、原文では "Небо очень и очень темное , а Земля голубоватая . " となっており、日本語では、「空は非常に暗かった。一方、地球は青みがかっていた」となる。朝日新聞4月13日夕刊、毎日新聞4月13日夕刊、読売新聞4月13日朝刊は、この記事を基にしてガガーリンの言葉を伝えている。

エラトステネスはどうやって地球の大きさを知ったのか – 2000年前とは思えぬ脅威の精度 | 数学の面白いこと・役に立つことをまとめたサイト

⇧  「地球は青かった」ってことは言ってなかったと...、2020年を迎え順調な正月太りを達成した、どうも、ボクです。

 

そんな地球ですが、

analytics-notty.tech

紀元前240年(約2000年前)、ギリシャ天文学者エラトステネスは、地球の大きさをはじめて測量した人物として知られています。

エラトステネスはどうやって地球の大きさを知ったのか – 2000年前とは思えぬ脅威の精度 | 数学の面白いこと・役に立つことをまとめたサイト

⇧  2000年前に測量されてたと!

ちなみに、正確な地球の半径は、6371kmです。その差は、 6371–6263=108 km であり、わずか1.7%の誤差しかありません。 約2000前の測量技術を考えるとこの誤差の小ささは驚異的といっていいでしょう。

エラトステネスはどうやって地球の大きさを知ったのか – 2000年前とは思えぬ脅威の精度 | 数学の面白いこと・役に立つことをまとめたサイト

⇧ エラトステネスさん、精度が高いっす!

今回は、そんな、エラトステネスさんが考案した「エラトステネスの篩」について調査してみました。

 

エラトステネスの篩って?

素数判定で、高速化って調べると、だいだい検索に出てくるやつです。

エラトステネスの篩 (エラトステネスのふるい、Sieve of Eratosthenes) は、指定された整数以下の全ての素数を発見するための単純なアルゴリズムである。古代ギリシアの科学者、エラトステネスが考案したとされるため、この名がある。

エラトステネスの篩 - Wikipedia

⇧  古代ギリシアで生まれた方法らしい。

素数判定のWikipediaにも、

ja.wikipedia.org

素数判定 - Wikipedia

⇧ 「エラトステネスの篩」は載っていると...というか「素数判定」の種類が多いな...。

 

 

高速化しないといけない時もありますと

素数判定のアルゴリズムのサンプルでJavaのものってなかなか見つからないんですが、

teratail.com

素数を判定する上では

2は素数
2以外の偶数は素数ではない
2以外の素数は奇数である

なんで外周のループは
ループ条件はm=3+2nで

素数判定のループはm/3回
※ 偶数(倍対象)は除外しているので奇数の最小値倍以上は判定不要

となる

Java - java問題 素数について|teratail

⇧  ってあったんで、参考に実装してみたのですが、

onlinejudge.u-aizu.ac.jp

f:id:ts0818:20200102225455p:plain

⇧  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 かかっていますと。

 

エラトステネスの篩で実装してみる

素数判定を速くするしかないんですが、ネットで調べると、「エラトステネスの篩」ぐらいしかヒットしないんですよね...

しかも、結構、「試し割り」を「エラトステネスの篩」と思って実装してる人も多いみたいです。

 

qiita.com

qiita.com

⇧  上記サイト様は、「エラトステネスの篩」を実装してくださっているようなので、参考にさせていただきました。 

0.011s になりました~!

f:id:ts0818:20200103113442p:plain

コーディングはこんな感じ。 

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⇧  上記サイト様が詳しいです。

 

まぁ、素数の研究に対する賞金がスゴイな~。

www.gizmodo.jp

今回見つかった素数は2325万桁台ですけど、1億桁の素数を最初に見つけた人類には、電子フロンティア財団(EFF)から15万ドル(約1666万円)の賞金が贈られますよ。グッドラック!

1億桁の賞金まであと1歩! FedEx社員が50番目の素数見つける。2325万桁 | ギズモード・ジャパン

⇧ 数学の知識が欲しいな~。

今回もモヤモヤ感が半端ないですが、「エラトステネスの篩」は結構速いらしいということが分かったということで。

今回はこのへんで。