Aritalab:Lecture/Algorithm/Eratosthenes

From Metabolomics.JP
< Aritalab:Lecture | Algorithm(Difference between revisions)
Jump to: navigation, search
m (大きな素数の求め方)
m (大きな素数の求め方)
Line 86: Line 86:
 
素数は数直線上にほぼ満遍なく分布しており、数が大きくなっても素数の割合はあまり変わりません。2013年、カナダ・モントリオール大のジェームズ・メイナードと、米カリフォルニア大のテレンス・タオが独立に「素数が2個含まれる幅 600 の区間が無限個存在する」ことを証明しています。つまり、エラトステネス手法で本当に大きな素数を求めるのは(素数リストが大きくなるので)無理ということです。
 
素数は数直線上にほぼ満遍なく分布しており、数が大きくなっても素数の割合はあまり変わりません。2013年、カナダ・モントリオール大のジェームズ・メイナードと、米カリフォルニア大のテレンス・タオが独立に「素数が2個含まれる幅 600 の区間が無限個存在する」ことを証明しています。つまり、エラトステネス手法で本当に大きな素数を求めるのは(素数リストが大きくなるので)無理ということです。
  
現在知られる最大の素数は1742万5170桁ですが、これはどうやって求めているのでしょう?これはメルセンヌ数の形になる素数だけを相手にしています。2<sup>n</sup> − 1 の形の数をメルセンヌ数といい、素数判定によく使われます(日本語版ウィキペディア:[https://ja.wikipedia.org/wiki/%E3%83%A1%E3%83%AB%E3%82%BB%E3%83%B3%E3%83%8C%E6%95%B0 メルセンヌ数])。
+
現在知られる最大の素数は1742万5170桁ですが、どうやって求めているのでしょう?これはメルセンヌ数の形になる素数だけを相手にしています。2<sup>n</sup> − 1 の形の数をメルセンヌ数といい、素数判定によく使われます(日本語版ウィキペディア:[https://ja.wikipedia.org/wiki/%E3%83%A1%E3%83%AB%E3%82%BB%E3%83%B3%E3%83%8C%E6%95%B0 メルセンヌ数])。
  
  

Revision as of 09:53, 24 July 2015

Contents

エラトステネスのふるい

ここでは素数をみつける最も簡単なアルゴリズム、「エラトステネスのふるい」を考えましょう。 まず動作のアニメーションとして日本語版ウィキペディアの記事「エラトステネスの篩」をみてください。

アルゴリズム1

なぜ x の平方根までで十分なの?
x の平方根を超える数 y が素数でない場合、y = ab という数の積に書けるはず。しかし a か b どちらかは x 以下になるので、既に除かれていることになります。
  1. 探索リストに 2 から x までの整数を並べる。
  2. 探索リストの先頭の数を素数リストに移動し、その倍数を探索リストから除く。
  3. 上記の操作を探索リストの先頭値が x の平方根に達するまで行う。
  4. 探索リストに残った数を素数リストに足して終了。

このアルゴリズムの利点は x の平方根まで計算するだけで x 以下の素数を全て得られるところです。しかしサイズ x の列をあらかじめ用意しなくてはなりません。100万以下の素数を求めるからといって、サイズ100万の列を用意するのはスペースの無駄です。そこで改良版を考えます。

アルゴリズム2

  1. 素数リストに2を入れる。
  2. 3 から x までの数 c について昇順に以下を繰り返す。
    1. c が素数リストにある数で割り切れるかチェック。
    2. c の平方根以下の素数で割り切れなかったら素数リストに追加。

この利点は探索リストが不要なところです。これなら大きい素数でも計算できます。具体的に20までの素数を計算してみましょう。偶数は必ず2で割れるのでスキップします。

  • c = 3, 素数リスト {2} : 素数リストの数で割り切れないのでリストに追加。
  • c = 5, 素数リスト {2,3} : 割り切れない
  • c = 7, 素数リスト {2,3,5} : 割り切れない
  • c = 9, 素数リスト {2,3,5,7} : 3 で割り切れる
  • c = 11, 素数リスト {2,3,5,7} : 割り切れない
  • c = 13, 素数リスト {2,3,5,7} : 割り切れない
  • c = 15, 素数リスト {2,3,5,7,13} : 3 で割り切れる
  • c = 17, 素数リスト {2,3,5,7,13} : 割り切れない
  • c = 19, 素数リスト {2,3,5,7,13,17} : 割り切れない
  • ...

このように進むプロセスを実際にJavaで書いてみましょう。

プログラム

以下のコードはJavaでそのまま実行できます。数字にLがついているのは long 指定で64ビット整数を使うためです。アルゴリズム2をそのままコードしています。

import java.util.Vector;

public class Eratosthenes {
  static public void main(String[] args) {
    Vector<Long> V = new Vector<Long>();
    V.addElement(2L);
    for (long c = 3L; c < 1000000L; c = c + 2L) {
      boolean flag = true;
      for (int i = 0; i < V.size(); i++) {
        long p = V.get(i);
        if (c < p * p)
          break;
        if (c % p == 0) {
          flag = false;
          break;
        }
      }
      if (flag)
        V.addElement(c);
    }
  System.out.println(V.elementAt(V.size() - 1));
  }
}

このプログラムを走らせると、ThinkPadX230 非力なノートPCでも2秒で100万以下の最大の素数 999,983 が求まりました。3や5の倍数は素数リスト V をスキャンせずに無視すれば実行時間は1秒以下になります。

素数のリストが記載されている外部のウェブページ をみても正しいことがわかります。

速度を測る方法

Javaにおいて実行速度 (ms単位) を測るには以下のようにします。

 long start = System.currentTimeMillis();
  ... 測りたいプログラムコード
 long end = System.currentTimeMillis();
 System.out.println(end-start);

100万以下の全ての素数を 1 秒で見つけられても、1000万以下の全ての素数が 10 秒で見つかるわけではありません。数が大きくなるにつれて素数リストが長くなるからです。上のプログラムの改良版では 1000万以下の素数全て (664579個) を見つけるのに 20 秒弱かかりました。(ちなみに1000万以下の最大の素数は999万9991です。)1億以下の全ての素数を求めるのには10分、10億以下の全ての素数になると何時間も待つことになります。

大きな素数の求め方

素数は数直線上にほぼ満遍なく分布しており、数が大きくなっても素数の割合はあまり変わりません。2013年、カナダ・モントリオール大のジェームズ・メイナードと、米カリフォルニア大のテレンス・タオが独立に「素数が2個含まれる幅 600 の区間が無限個存在する」ことを証明しています。つまり、エラトステネス手法で本当に大きな素数を求めるのは(素数リストが大きくなるので)無理ということです。

現在知られる最大の素数は1742万5170桁ですが、どうやって求めているのでしょう?これはメルセンヌ数の形になる素数だけを相手にしています。2n − 1 の形の数をメルセンヌ数といい、素数判定によく使われます(日本語版ウィキペディア:メルセンヌ数)。


発展:メルセンヌ合成数

メルセンヌ数が合成数の場合、このウェブサイトに記載される定理3より、2n − 1 を構成する素数の片方は 2 n + 1 の形に書けることがわかります。3と5、7と73、23と89の積はメルセンヌ合成数ですが、次のようになっています。

  • 3 * 5 = 24 - 1 → 4 + 1 = 5
  • 7 * 73 = 29 - 1 → 9 * 8 + 1 = 73
  • 23 * 89 = 211 - 1 → 11 * 8 + 1 = 89

同じページの定理4からメルセンヌ数を構成するには 4n + 3 型の素数における n が

2 n + 1 が modulo 3 の素数

という条件を満たすことがわかります。3と5、7と73、23と89の例でいうと

  • 3 (n=0) → 2n+1 = 1 素数
  • 7 (n=1) → 2n+1 = 3 素数
  • 23 (n=5) → 2n+1 = 11 素数

となっています。

Personal tools
Namespaces

Variants
Actions
Navigation
metabolites
Toolbox