素数単語

ソスウ
2.5千文字の記事
  • 16
  • 0pt
掲示板へ

素数prime number)とは、自然数のうち自身と1でしか割り切ることのできない数のことである。但し1を除く。

暗号理論や精安定剤として重用される。

素数の一覧(1000未満)

2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997,...

続きがもっと見たい、という方は「素数の一覧」記事を参照。

数学的性質

素数という概念は、紀元前1600年ごろには(部分的にだが)知られていたようである(ソースWikipedia)。にも関わらず、双子素数の予想、ゴールドバッハの予想、リーマン予想など、素数に関連する多くの予想が現在も未解決のままである。それゆえか、素数は秘的な数と言われたりもする。

また、大きな数の素因数分解困難であるため、暗号理論に応用されている。

環論における既約元、素元は、素数の概念一般化である。

素数は無限に存在する

有名なユークリッドによる明(『原論』第9巻命題20, 紀元前3世紀頃)を紹介する。他にもたくさんの明が存在する。詳しくは素数が無数に存在することの証明 - Wikipediaexitを参照。

素数が有限個しか存在しないと仮定する。素数の全体を p1, p2, ... , pn とおく。ここで、新たな数 p = p1×p2× ... × pn +1 を考える。p を p1 で割った余りは1だから、p は p1 で割り切れない。同様に p2, ... , pn でも割り切れない。よって p は素数である。一方、 p はどの p1, p2, ... , pn よりも大きい。だがこれは素数の全体が p1, p2, ... , pn であることに矛盾する。よって素数は限に存在する。

素数定理

素数が自然数の中にどのぐらいの「割合」で存在するのかを示唆する定理であり、18世紀末ガウスやルジャンドルによって予想され、1896年にプーサンとアダマールによって独立明された。詳しくは素数定理 - Wikipediaexitを参照。

正の実数 x に対して、x 以下の素数の個数を π(x) と表す。このとき、π(x) と x/log x の増加速度は "同じぐらい" である。正確に言うと、 limx→ π(x) / (x/log x) = 1 が成り立つ。

2019年1月現在確認されている最大の素数

282589933-1である。(2018年12月にGIMPSにより発見exit

十進数で2486万2048桁にも及ぶ。

また、メルセンヌ素数(2n-1で表せる素数)の中で人類が発見したものを小さい順に並べたとき、51番に来るメルセンヌ素数である。ちなみに、1〜47番メルセンヌ素数までは「隙間なく」発見されているが、47, 48, 49, 50, 51番メルセンヌ素数の間にまだ発見されていないメルセンヌ素数が存在するのかどうかはわかっていない(2019年1月現在)。詳しくはメルセンヌ数exitおよび巨大な素数の一覧exit(いずれもWikipedia)を参照。

100以下の素数の覚え方

さん 五時に セブン イレブン 父さん 「いーな」と ついて いく。
2 3 5 7 11 13 17 19
兄さん 屋に さぁ行こう。 南は 良いとこ。 与作 死なない。
23 29 31 37 41 43 47
誤算の 悟空 6位。 しく ない。
53 59 61 67 71
奈々さん 泣くな。 ハチさん 吐くな。 苦難のを乗り越えよう。
73 79 83 89 97

素数の利用例

『落ち着け、素数を数えるんだ。』

上記台詞漫画ジョジョの奇妙な冒険ストーンオーシャン」にてプッチ神父が使用したことにより、慌てふためいた発言や言動に対して落ち着かせるために使用される。神父く、「素数は1と自分の数でしか割ることのできない孤独数字・・・。わたし勇気を与えてくれる」

ただしこれは「素数を数えれば落ち着く」元ネタではく、それ以前でもスティーブン・キング小説などで見られた表現である。

またニコニコ動画内では、動揺するような場面が出てきた場合、「2、3、5、7、11、13……」と素数をコメントしたり、動画内で素数を数えるMADが出てきたりなど、様々な活用が見られる。

もっとも、動揺しすぎて「2、4、6、8・・・」となぜか偶数を数え始めるものや、⑨を素数とするものも多数存在している。

関連動画・静画

関連商品

関連項目・関連タグ

【スポンサーリンク】

  • 16
  • 0pt
スマホ版URL:
https://dic.nicovideo.jp/t/a/%E7%B4%A0%E6%95%B0
記事編集 編集履歴を閲覧

この記事の掲示板に最近描かれたお絵カキコ

この記事の掲示板に最近投稿されたピコカキコ

ピコカキコがありません

素数

213 ななしのよっしん
2022/03/31(木) 11:00:18 ID: cdGoA5o26+
(3以上の奇数)×(3以上の奇数)
=x,yを自然数として、(2x+1)(2y+1)
=2x+4xy+2y+1
=2(x+2xy+y)+1

凡人はここでx+2xy+yが意味不明で撤退する。ラマヌジャンなら進む。
なぜならx+2xy+yが取らない自然数を2倍して+1したら素数だから。
x+2xy+yは対称式だから
計算するのはxy面で1≦x,1≦y,y≦xの領域に含まれる格子点だけでいい。

ただ実際に計算するにあたってはxとyの上界を決めておかないと計算が永遠に終了しない。それぞれの上界をM,Nとしよう。
計算するのはxy面で1≦x≦M,1≦y≦N,y≦xの領域に含まれる格子点。
214 ななしのよっしん
2022/03/31(木) 11:11:52 ID: cdGoA5o26+
イキってるわけじゃない。イライラしてんの。プログラムまで書いて提出して、さらには実際に計算した結果も提示したのに理解されなくて立ってんだ。どっからどう説明したら理解してくれるんだ状態。ヒステリックになってる。
215 ななしのよっしん
2022/03/31(木) 11:15:38 ID: Nn9zRUuAgD
匿名掲示版に向いてない性格だってことだけは十二分にわか
群論の記事にも似たようながいたな…
216 ななしのよっしん
2022/03/31(木) 11:21:22 ID: cdGoA5o26+
以下プログラムに71突っ込んだ結果

自然数を入してください
3以上143以下の範囲に含まれる素数以外の奇数は以下の通りです
9, 15, 21, 25, 27, 33, 35, 39, 45, 45, 49, 51, 55, 57, 63, 63, 65, 69, 75, 75, 77, 81,
81, 85, 87, 91, 93, 95, 99, 99, 105, 105, 105, 111, 115, 117, 117, 119, 121, 123,
125, 129, 133, 135, 135, 135, 141, 143,

4以上間いてるとこ見つけたらその間にある奇数はどう見ても素数だろ。
217 ななしのよっしん
2022/03/31(木) 11:23:54 ID: cdGoA5o26+
<<215
ストレスの捌け口にしてしまってた感はある。一旦時間をおくよ。すまない。ありがとう。
218 ななしのよっしん
2022/03/31(木) 11:24:23 ID: Gxsgv66f2P
>>209
素人質問で申し訳ないですが、何故2の倍数を最初に除いたのでしょう?
もしかしたらプログラミング的には意味のあることなのかもしれないですが、
数学的には「自然数から1と(2以上の自然数a)×(2以上の自然数b)を除いたもの」で事足ります
219 ななしのよっしん
2022/03/31(木) 12:40:42 ID: 2hRCn0ByzH
考え方は問題ない
合成数の補集合素数かつ全ての奇数合成数を上げることができる
はじめの方で書いてた結果が重複する問題はx>yの条件を付けずxもyも1からn-1まで走査するから
偶数をはじめから弾くのは通常は計算量を減らすため
計算量がおおよそ1/4になるからやらない手はない

問題があるとするならエラトステネスの篩劣化になっているところ
エラトステネスの篩はxが合成数ならそもそも計算しないがこプログラムでは素数でも合成数でもとりあえず計算することになるのでnが100万とかになってくると顕著な差が出てくると思う
220 ななしのよっしん
2022/03/31(木) 12:47:48 ID: 2hRCn0ByzH
すまんちょっと違った
分岐で合成数かどうか判定する計算の速さと2数のかけ算の速さの差で計算量に違いが出るからあんまり変わらんかもしれん
かけ算は桁が多くなればなるほど計算量が増えるけどエラトステネスの篩では別の表に合成数か素数かの判定を格納しておけばいいから桁数によらず判定できるので工夫次第なところはある
221 ←素数であるか?
2022/05/03(火) 17:35:46 ID: i89fV4m726
答:素数ではありません。
221=13×17の合成数なのです。
222 ななしのよつしん
2022/05/03(火) 17:38:21 ID: i89fV4m726
93187(クサイハナ)は素数です。