与えられた自然数が素数であるか合成数であるかを判定するためのアルゴリズムが多数考案されている。最も素朴な方法は、から以下の素数まで順番に割っていく、試し割り法と呼ばれる方法である。が以下の全ての素数で割り切れなければは素数である。試し割り法は、が大きくなるに従って、急速に速度が低下するため、実用的ではない。任意の数に適用できる試し割り法よりも高速なアルゴリズムが考案されている。また、特殊な形をした数に対してはより高速なアルゴリズムも存在する。素数判定は、与えられた数が素数であるか否かだけを判定するものであるが、素因数分解とはより強く、与えられた数の全ての素因数を列挙することであるとも言える。分布.ある自然数までにどのくらいの素数があるのかという問題は、基本的だが非常に難しい問題である。以下の素数の個数を(素数計数関数)とすると、次のような定理もある。一方で、例えばとの間に素数が存在するかという問題は未解決である(ルジャンドル予想)。素数が全く無い区間は、いくらでも長いものがあることが知られている。に対して、連続する個の自然数はそれぞれ、それらより小さいで割り切れるので、どれも素数でない。は任意にとれるから、素数が全く無いいくらでも長い区間があると言える。これは一例にすぎず、実際にはもっと小さい所で、素数が全く無い長い区間が生じるようである。例えば、からまで個連続で合成数である。素数計数.素数に関連する主な性質.素数の逆数和.素数の逆数の和は(無限大に)発散する。この命題は『素数は無数に存在する』という命題を含んでいる(有限個ならば収束、すなわち発散しないはずである)が、それだけではなく素数の分布に関してより多くの情報を提供している。この結果は最初にレオンハルト・オイラーによりゼータ関数を研究することでもたらされた。以下の証明はポール・エルデシュによる、より直接的で、また簡潔な証明である。素数が無数に存在することを証明に用いないため、その証明をも含んでいる。素数の逆数和は収束すると仮定する。番目の素数をで表すと、を満たすが存在する。以下の自然数のうち最大素因数が以下のものからなる集合をとする。任意のに対して、と表示すると、は高々通り、より