例えば19^2(=361)未満の数は2×3×5×7×11×13×17=510510と互いに素なら素数。ユークリッドの互除法(割った余りを使う計算法)なら数ステップ。例)317は？(510510,317)=(317,140)=(140,37)=(37,29)=1より素数です。