Aritalab:Lecture/Algorithm/Eratosthenes
Line 26: | Line 26: | ||
この利点は探索リストが不要なところです。これなら大きい素数でも計算できます。実際にJavaで書いてみましょう。 | この利点は探索リストが不要なところです。これなら大きい素数でも計算できます。実際にJavaで書いてみましょう。 | ||
− | + | ==プログラム== | |
− | 以下のコードはJavaでそのまま実行できます。数字にLがついているのは long | + | 以下のコードはJavaでそのまま実行できます。数字にLがついているのは long 指定で64ビット整数を使うためです。アルゴリズム2をそのままコードしています。 |
<small> | <small> | ||
<pre> | <pre> | ||
Line 56: | Line 56: | ||
このプログラムを走らせると、2秒で100万以下の最大の素数 999,983 が求まりました(ThinkPadX230 非力なノートPCです)。素数のリストが記載されている[http://www.usamimi.info/~geko/arch_acade/elf009_prime/list100.html 外部のウェブページ] をみても正しいことがわかります。 | このプログラムを走らせると、2秒で100万以下の最大の素数 999,983 が求まりました(ThinkPadX230 非力なノートPCです)。素数のリストが記載されている[http://www.usamimi.info/~geko/arch_acade/elf009_prime/list100.html 外部のウェブページ] をみても正しいことがわかります。 | ||
− | === | + | ===速度を測る方法=== |
− | + | Javaにおいて実行速度 (ms単位) を測るには以下のようにします。 | |
− | + | <small><pre> | |
+ | long start = System.currentTimeMillis(); | ||
+ | ... 測りたいプログラムコード | ||
+ | long end = System.currentTimeMillis(); | ||
+ | System.out.println(end-start); | ||
+ | </pre></small> | ||
+ | |||
+ | |||
+ | ==大きな素数の求め方== | ||
+ | 素数は数直線上にほぼ満遍なく分布しており、数が大きくなっても素数の割合はあまり変わりません。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 メルセンヌ数])。 | ||
+ | |||
+ | |||
+ | ===メルセンヌ合成数=== | ||
+ | メルセンヌ数が合成数の場合、[http://primes.utm.edu/mersenne/index.html このウェブサイト]に記載される定理3より、2<sup>n</sup> − 1 を構成する素数の片方は 2 n + 1 の形に書けることがわかります。3と5、7と73、23と89の積はメルセンヌ合成数ですが、次のようになっています。 | ||
+ | |||
+ | * 3 * 5 = 2<sup>4</sup> - 1 → 4 + 1 = 5 | ||
+ | * 7 * 73 = 2<sup>9</sup> - 1 → 9 * 8 + 1 = 73 | ||
+ | * 23 * 89 = 2<sup>11</sup> - 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 素数 | ||
+ | |||
+ | となっています。 |
Revision as of 20:24, 23 July 2015
Contents |
エラトステネスのふるい
ここでは素数をみつける最も簡単なアルゴリズム、「エラトステネスのふるい」を考えましょう。 まず動作のアニメーションとして日本語版ウィキペディアの記事「エラトステネスの篩」をみてください。
アルゴリズム1
なぜ x の平方根までで十分なの? |
---|
x の平方根を超える数 y が素数でない場合、y = ab という数の積に書けるはず。しかし a か b どちらかは x 以下になるので、既に除かれていることになります。 |
- 探索リストに 2 から x までの整数を並べる。
- 探索リストの先頭の数を素数リストに移動し、その倍数を探索リストから除く。
- 上記の操作を探索リストの先頭値が x の平方根に達するまで行う。
- 探索リストに残った数を素数リストに足して終了。
このアルゴリズムの利点は x の平方根まで計算するだけで x 以下の素数を全て得られるところです。しかしサイズ x の列をあらかじめ用意しなくてはなりません。100万以下の素数を求めるからといって、サイズ100万の列を用意するのはスペースの無駄です。そこで改良版を考えます。
アルゴリズム2
- 素数リストに2を入れる。
- 2から x までの数 c について昇順に以下を繰り返す。
- c が素数リストにある数で割り切れるかチェック。
- c の平方根以下の素数で割り切れなかったら素数リストに追加。
この利点は探索リストが不要なところです。これなら大きい素数でも計算できます。実際に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)); } }
このプログラムを走らせると、2秒で100万以下の最大の素数 999,983 が求まりました(ThinkPadX230 非力なノートPCです)。素数のリストが記載されている外部のウェブページ をみても正しいことがわかります。
速度を測る方法
Javaにおいて実行速度 (ms単位) を測るには以下のようにします。
long start = System.currentTimeMillis(); ... 測りたいプログラムコード long end = System.currentTimeMillis(); System.out.println(end-start);
大きな素数の求め方
素数は数直線上にほぼ満遍なく分布しており、数が大きくなっても素数の割合はあまり変わりません。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 素数
となっています。