素数（そすう、）とは、自然数で、正の約数が と自分自身のみであるもののことで、ただし は（現在では）含めない。正の約数の個数が 2 である自然数と言い換えることもできる。 でない自然数で素数でないものは合成数と呼ばれる。一般には、素数は代数体の整数環の素元として定義される（そこでは反数などの同伴なものも素数に含まれる）。このため、有理整数環での素数は有理素数と呼ばれることもある。最小の素数は で、素数は無数に存在する。したがって、素数からなる無限数列が得られる。素数は無数に存在することは、紀元前3世紀頃のユークリッドの著書『原論』で既に証明されていた。自然数あるいは実数の中での素数の分布の様子は高度に非自明で、リーマン予想などの現代数学の重要な問題との興味深い結び付きが発見されている。分散コンピューティング・プロジェクト GIMPS により、史上最大の素数の探求が行われている。現在で知られている最大の素数は、2016年1月に発見された、現在分かっている中で49番目のメルセンヌ素数 であり、十進法で表記したときの桁数は2233万8618桁に及ぶ。素数とは、自明な正の約数（ と自分自身）以外に約数を持たない自然数であり、 でない数のことである。つまり、正の約数の個数が 2 である自然数のことである。例えば、 は、正の約数が のみなので素数である。一方で は、正の約数が なので素数でない。素数でない 以上の自然数を合成数と呼ぶ。また、特に でない素数は奇数であり、奇素数と呼ぶ。十進法表示では、 以外の素数は、一の位が のいずれかである。100以下の素数は、小さい順に次の通りである。さらに、1000以下の素数は以下の通りである。「 以上の自然数は、素数の積で表せる。その表し方は積の順序を除けば一意である」という、素因数分解の可能性・一意性が成立する（算術の基本定理）。すなわち、「素数全体」の成す集合は、自然数全体の成す集合の（乗法に関する）最小の生成系である。俗な表現をすると、これは「素数は自然数の構成要素である」などとなる。素数の定義である「 と自分自身でしか割り切れない」という条件（既約性）は、抽象代数学において、環の既約元の概念（一部の環では素元の概念と一致する）に抽象化され一般的に取り扱われる。一般の環で、任意の元は既約元の積に分解され、しかもその表示は一意であるという性質は稀有である。例えばネーター環では、任意の元は既約元分解が可能であるが、その表示が一意ではないネーター環の例はいくつも知られている。一意に既約元分解ができる環は一意分解環と呼ばれ、既約元分解は素元分解ともなる。素数の定義を「自明でない（ と自分自身以外）約数の積に分解できない自然数」と考えた場合、「 を素数の定義に含めるか含めないか」が問題となる。古代ギリシアでは、 はそもそも数（自然数）であるとさえ見なされなかったので、 は素数ではなかった。一方、19世紀には、 は素数であると考える数学者が多く存在した。例えば、レーマーの までの素数表（後の1956年に再版）では、素数は から始まるものとして書かれている。アンリ・ルベーグは、 を素数だと考えた最後の専門的な数学者だと言われている。と無数の素因数分解を与えることになり、一意性が成り立たなくなる。さらに、 以外の素数で成り立つ様々な性質がある（例えば、自然数とそれに対応するオイラーのφ関数や約数和函数の値との関係など）。紀元前1600年頃のエジプト第2中間期において、素数に関する知識が部分的に知られていたことが、リンド数学パピルスなどの資料によって示唆されている。例えば分数をエジプト式分数で表す場合、素数と合成数の場合で異なる計算をしなければならないからである。しかし、記録に残っている限りにおいて、明確に素数を研究対象としたのは古代ギリシア人が最初である。紀元前約300年頃に書かれたユークリッドの『原論』には素数が無数に存在することや素因数分解の一意性が証明されている。また、ユークリッドはメルセンヌ素数から完全数を構成する方法を示している。ギリシアの数学者、エラトステネスに因んで名付けられたエラトステネスの篩（ふるい）は、素数を列挙するための計算方法である。古代ギリシア時代の後、17世紀になるまで素数の研究にはそれほどの進展が無かった。1640年に、ピエール・ド・フェルマーはフェルマーの小定理を（未証明ではあるが）述べた。この定理は後にライプニッツとオイラーによって証明された。素数が無数に存在することは既に古代ギリシア時代から知られていて、ユークリッドが彼の著作『原論』の中で証明している。上記のユークリッドによる証明以外にも、素数が無数に存在することの証明方法が存在する。与えられた自然数 が素数であるか合成数であるかを判定するためのアルゴリズムが多数考案されている。最も素朴な方法は、 から 以下の素数まで順番に割っていく、試し割りと呼ばれる方法である。 が 以下の全ての素数で割り切れなければ は素数である。試し割りは、 が大きくなるに従って、急速に速度が低下するため、実用的ではない。任意の数に適用できる試し割りよりも高速なアルゴリズムが考案されている。また、特殊な形をした数に対してはより高速なアルゴリズムも存在する。素数判定は、与えられた数が素数であるか否かだけを判定するものであるが、素因数分解とはより強く、与えられた数の全ての素因数を列挙することであるとも言える。ある自然数までにどのくらいの素数があるのかという問題は、基本的だが非常に難しい問題である。素数のない、いくらでも長い区間が存在する。例えば、 に対して、連続する 個の自然数 はそれぞれ、より小さい で割り切れるので、どれも素数でない。また、比較的小さな数では、 から まで個連続で合成数である。（この区間の最初の値はを、終了の値はをその区間幅についてはを参照）これに関して、次の素数定理は有名である。この定理は1896年に、アダマールとド・ラ・ヴァレ・プサンによって独立に証明された。が成り立つ。この定理は、1792年に15歳のカール・フリードリヒ・ガウスによって予想されていた（ガウスが最初に予想したのかどうかは不明）。この定理の証明は、ゼータ関数と複素関数論を用いる高度なものであったが、1949年にアトル・セルバーグとポール・エルデシュは独立に初等的な証明を与えた。この評価式はリーマン予想を仮定すると大幅に精度をよくすることができる。次のような定理もある。この主張は「任意の素数 の次の素数は 未満」とも言い換えられる。したがって、現在知られている最大の素数 の次の素数は 未満である。しかしながら、例えば と の間に素数が存在するかという問題は未解決である（ルジャンドル予想）。素数の逆数の和は（無限大に）発散する。この命題は『素数は無数に存在する』という命題を含んでいる（有限個ならば収束、すなわち発散しないはずである）が、それだけではなく素数の分布に関してより多くの情報を提供している。この結果は最初にレオンハルト・オイラーによりゼータ関数を研究することでもたらされた。以下の証明はポール・エルデシュによる、より直接的で、また簡潔な証明である。素数が無数に存在することを証明に用いないため、その証明をも含んでいる。素数の逆数和は収束すると仮定する。 番目の素数を で表すと、を満たす が存在する。と表示すると、 は高々 通り、 より(2), (3) より , ∴ 。これは の任意性に矛盾。（証明終）双子素数に限ると、逆数和は に収束することが証明されている（ブルン定数）。オイラーの発見した式、 は、 で全て素数となる。これは、虚二次体 formula_4 の類数が であることと関係している。多変数の高次多項式では、全ての素数を生成することができる式がいくつか知られている。例えば、 が素数となる必要十分条件は、次のディオファントス方程式が自然数解を持つことである:誤解されやすいが、素数が無数に存在することの、#ユークリッドによる証明で使われる手順からは、必ずしも素数を得ることができない。なぜなら最初の仮定「最大の素数 が存在する」が正しくないからである。実際に、 でと、自明でない約数に分解できてしまう（最小の反例）。長い間、数論、その中でもとりわけ素数に関する研究は、その分野以外での応用の全くない純粋数学の見本と見なされていた。特に、イギリスの数論研究者であるハーディは、自身の研究が軍事的に何の重要性も持たないことを誇っていた。しかし、この見方は1970年代には覆されてしまった。素数が公開鍵暗号のアルゴリズムに使用できると広く知られるようになったためである。現在では素数はハッシュテーブルや擬似乱数生成にも用いられ、工学的応用上重要度の高いものとなっている。公開鍵暗号のアルゴリズムとして、RSA暗号やディフィー・ヘルマン鍵共有といった、大きな数の素因数分解は困難であるという性質に基礎を置くものがある。RSA暗号は、2つの（大きな）素数の掛け算は比較的簡単に（効率的に）行えるが、その積を素因数分解して元の2つの素数を求めることは難しいという事実に基づいている。自然界に現れる素数の一例として、素数ゼミと呼ばれるセミの一種がいる。アメリカ合衆国に分布するこのセミの成虫は、ある周期ごとに、13年ないしは17年間の周期で大量発生する。成虫になった後は、数週間だけを地上で成虫として過ごし交配と産卵を行う。このセミが素数周期で発生する理由として、寄生虫や捕食者に対抗するための進化であるという説や近縁種との交雑を避けるためであるという説がある。つまり、もしこのセミが12年の発生周期を持っていた場合、12の約数である2, 3, 4, 6年の寿命を持つ捕食者と同時に発生してしまうことになり、捕食対象にされやすくなる。また、地理的に近い場所で12年周期と15年周期のセミが存在した場合、60年ごとに2種は同時に発生し、交雑してしまう可能性がある。すると、雑種は発生周期がズレてしまい、同種のセミとの交尾の機会が失われる。素数の周期を持つものは交雑が起こりにくく、淘汰されにくいと考えられる。また、ゼータ関数上の零点の分布の数式が、原子核のエネルギー間隔を表す式と一致することを示し、素数と核物理現象との関連性が示唆されている。整数の平方根や円周率などのように、素数にも語呂合わせによる記憶術がある。以下に挙げる。

出典:wikipedia