素数であるか合成数であるかを判定するためのアルゴリズムが多数考案されている。以下の素数まで順番に割っていく、試し割りと呼ばれる方法である。大きくなるに従って、急速に速度が低下するため、実用的ではない。任意の数に適用できる試し割りよりも高速なアルゴリズムが考案されている。特殊な形をした数に対してはより高速なアルゴリズムも存在する。素数判定は、与えられた数が素数であるか否かだけを判定するものであるが、素因数分解とはより強く、与えられた数の全ての素因数を列挙することであるとも言える。分布[編集]ある自然数までにどのくらいの素数があるのかという問題は、基本的だが非常に難しい問題である。素数のない、いくらでも長い区間が存在する。割り切れるので、どれも素数でない。まで13個連続で合成数である。A008996を参照)これに関して、次の素数定理は有名である。この定理は1896年に、アダマールとド・ラ・ヴァレ・プサンによって独立に証明された。この定理は、1792年に15歳のカール・フリードリヒ・ガウスによって予想されていた(ガウスが最初に予想したのかどうかは不明)。この定理の証明は、ゼータ関数と複素関数論を用いる高度なものであったが、1949年にアトル・セルバーグとポール・エルデシュは独立に初等的な証明を与えた。この評価式はリーマン予想を仮定すると大幅に精度をよくすることができる。次のような定理もある。未満」とも言い換えられる。間に素数が存在するかという問題は未解決である(ルジャンドル予想)。1017個)を計算したと報告した[12][13]が、結果は保存されていない。素数計数関数を計算するには、実際に素数を数えるより高速な公式が存在する。2×1021個)の素数があると計算された。2×1022個)の素数が存在する[14]。素数に関連する主な性質[編集]素数の逆数和[編集]素数の逆数の和は(無限大に)発散する。この命題は『素数は無数に存在する』という命題を含んでいる(有限個ならば収束、すなわち発散しないはずである)が、それだけではなく素数の分布に関してより多くの情報を提供している。この結果は最初にレオンハルト・オイラーによりゼータ関数を研究することでもたらされた。素数が無数に存在することを証明に用いないため、その証明をも含んでいる。素数の逆数和は収束すると仮定する。