まず、正の整数 n は必ず正の整数 x、y を用いて n = xy と表すことができる。 たとえば n = 10 である時、x と y の組み合わせは


( x, y ) = ( 1, 10 )
         ( 2,  5 )
         ( 5,  2 )
         ( 10, 1 ) の４つである。


ここで注目して欲しいのは x と y が上下に対称的に登場していることである。 加えて、n = xy において n と x がわかっている時 y は一意に定まることを考えれば掛け算の片方だけ( x と y の片方だけ )を考えれば良い。


なのでこの時に考えるべき因数は x = 1, 2 の２つのみである。 そして、全ての整数は１で割り切れるので探索する必要がないことを考慮すると、 n = 10 の素数探索において考えるべき整数は2以上であるので x = 2 のみであると言える。


次に x と y が上下に対称的になる境界線を考える。
n = xy において x = y が成り立つのは x = √n の時であり、x が √n を超えた後に登場する数字は x と y の対称性を考えると既に登場していると言える。
( n = 100 の時の x と y を全て書き出してみれば直感的に理解できるであろう。)


以上のことより、正の整数 n が素数かどうかを判定するのに探索するべき整数は 2 以上 √n 以下に収まる。