試し割り法
最悪計算量を考えると、試し割り法は非常に時間のかかるアルゴリズムである。2進法でのn桁の数aに対して、2から順にaの平方根まで試すアルゴリズムは
π ( 2 n / 2 ) ≈ 2 n / 2 ( n 2 ) ln  2 {\displaystyle \pi (2^{n/2})\approx {2^{n/2} \over \left({\frac {n}{2}}\right)\ln 2}}
回の割り算を行う。
ここで、 π ( x ) {\displaystyle \pi (x)} は素数計数関数であり、x未満の素数の数である。これは約数の候補として素数を取得する素数判定のオーバヘッドを説明しきるものではない。便利なテーブルはそこまで大きくなく、符号つき16ビット整数の範囲内の最大の素数であればP(3512)=32749、符号なし16ビット整数の範囲内での最大の素数であればP(6542)=65521である。
このテーブルを使うことによって、65537 =4,295,098,369までの素数判定が可能である。このようなテーブルはエラトステネスの篩でも用いられ、大規模な素数判定には有用であるが、その一方で単純に2とnの平方根以下の奇数のみで素数判定を行う手法も存在する。その場合には、n桁の数を判定するためにかかる計算はおよそ 2 n / 2 {\displaystyle 2^{n/2}} である。