Aritalab:Lecture/Algorithm/Eratosthenes - Revision history

Adm: /* 大きな素数の求め方 */

2015-07-28T07:06:04Z

‎大きな素数の求め方

Adm: /* 大きな素数の求め方 */

2015-07-28T02:55:37Z

‎大きな素数の求め方

Adm: /* 大きな素数の求め方 */

2015-07-28T01:50:57Z

‎大きな素数の求め方

Adm: /* プログラム */

2015-07-24T01:17:26Z

‎プログラム

Adm: /* 大きな素数の求め方 */

2015-07-24T01:14:26Z

‎大きな素数の求め方

Adm: /* 大きな素数の求め方 */

2015-07-24T00:53:31Z

‎大きな素数の求め方

Adm: /* 大きな素数の求め方 */

2015-07-24T00:53:13Z

‎大きな素数の求め方

Adm: /* 大きな素数の求め方 */

2015-07-24T00:52:45Z

‎大きな素数の求め方

Adm: /* プログラム */

2015-07-24T00:52:12Z

‎プログラム

Adm: /* 大きな素数の求め方 */

2015-07-24T00:43:50Z

‎大きな素数の求め方

@@ Line 86: / Line 86: @@
 素数は数直線上にほぼ満遍なく分布しており、数が大きくなっても素数の割合はあまり変わりません。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 メルセンヌ数])。16世紀フランスの神学者メルセンヌが、2<sup>n</sup>  − 1 が素数になるのは、n ≤ 257 では、n = 2, 3, 5, 7, 13, 17, 19, 31, 67, 127, 257 であると主張したことに由来します（でもいくつか間違っていました）。メルセンヌ素数のリストは[http://primes.utm.edu/mersenne/index.html Chris K. Caldwellのサイト]や[http://www.mersenne.org/primes/ GIMPSプロジェクトのページ]で見られます。
+現在知られる最大の素数は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 メルセンヌ数])。16世紀フランスの神学者メルセンヌが、2<sup>n</sup>  − 1 が素数になるのは、n ≤ 257 では、n = 2, 3, 5, 7, 13, 17, 19, 31, 67, 127, 257 であると主張したことに由来します（いくつか間違っている）。メルセンヌ素数のリストは[http://primes.utm.edu/mersenne/index.html Chris K. Caldwellのサイト]や[http://www.mersenne.org/primes/ GIMPSプロジェクトのページ]で見られます。
 ====参考====

@@ Line 86: / Line 86: @@
 素数は数直線上にほぼ満遍なく分布しており、数が大きくなっても素数の割合はあまり変わりません。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 メルセンヌ数])。16世紀フランスの神学者メルセンヌが、2<sup>n</sup>  − 1 が素数になるのは、n ≤ 257 では、n = 2, 3, 5, 7, 13, 17, 19, 31, 67, 127, 257 であると主張したことに由来します（でもいくつか間違っていました）。メルセンヌ素数のリストは[http://primes.utm.edu/mersenne/index.html Chris K. Caldwellのサイト]で見られます。
+現在知られる最大の素数は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 メルセンヌ数])。16世紀フランスの神学者メルセンヌが、2<sup>n</sup>  − 1 が素数になるのは、n ≤ 257 では、n = 2, 3, 5, 7, 13, 17, 19, 31, 67, 127, 257 であると主張したことに由来します（でもいくつか間違っていました）。メルセンヌ素数のリストは[http://primes.utm.edu/mersenne/index.html Chris K. Caldwellのサイト]や[http://www.mersenne.org/primes/ GIMPSプロジェクトのページ]で見られます。
 ====参考====

@@ Line 86: / Line 86: @@
 素数は数直線上にほぼ満遍なく分布しており、数が大きくなっても素数の割合はあまり変わりません。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 メルセンヌ数])。16世紀フランスの神学者メルセンヌが、2<sup>n</sup>  − 1 が素数になるのは、n ≤ 257 では、n = 2, 3, 5, 7, 13, 17, 19, 31, 67, 127, 257 であると主張したことに由来します（でもいくつか間違っていました）。メルセンヌ素数のリストは[http://primes.utm.edu/mersenne/index.html Chris K. Caldwellのサイト]で見られます。
 ====参考====

@@ Line 67: / Line 67: @@
+}
 </pre></small>
-このプログラムを走らせると、ThinkPadX230 非力なノートPCでも2秒で100万以下の最大の素数 999,983 が求まりました。3や5の倍数は素数リスト V をスキャンせずに無視すれば実行時間は1秒以下になります。
+このプログラムを走らせると、ThinkPadX230 という非力なノートPCでも2秒で100万以下の素数全てが求まりました（最後は999,983）。プログラムが少し長くなりますが3や5の倍数は素数リスト V をスキャンせずに無視するようにすると、実行時間は1秒以下になります。
-素数のリストが記載されている[http://www.usamimi.info/~geko/arch_acade/elf009_prime/list100.html 外部のウェブページ] をみても正しいことがわかります。
+素数のリストが記載されている[http://www.usamimi.info/~geko/arch_acade/elf009_prime/list100.html 外部のウェブページ] をみてもこの結果が正しいことがわかります。
 ===速度を測る方法===

@@ Line 86: / Line 86: @@
 素数は数直線上にほぼ満遍なく分布しており、数が大きくなっても素数の割合はあまり変わりません。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 メルセンヌ数])。
 ===発展：メルセンヌ合成数===

← Older revision		Revision as of 00:53, 24 July 2015
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 メルセンヌ数])。

@@ Line 84: / Line 84: @@
 ==大きな素数の求め方==
-素数は数直線上にほぼ満遍なく分布しており、数が大きくなっても素数の割合はあまり変わりません。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 メルセンヌ数])。

← Older revision		Revision as of 00:43, 24 July 2015
Line 83:		Line 83:
	素数は数直線上にほぼ満遍なく分布しており、数が大きくなっても素数の割合はあまり変わりません。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 メルセンヌ数])。