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