素数と判定させるアルゴリズム

合成数(素数でない数)xは$p <= \sqrt{x}$を満たす素因子pをもつ。

という性質があります。

これを利用すれば、xが素数かどうか調べるには、2からx - 1まででなく
2から$\sqrt{x}$までの値で割り切れるかどうか調べればいいので、
$O(\sqrt{x})$のアルゴリズムにすることができます。

このアルゴリズムを疑似言語で実装すると以下のようになります。

疑似言語による素数と判定するアルゴリズム

isPrime(x)
 if x == 2
  return true

 if x < 2 または xが偶数
  return false

 i = 3
 // 平方根以下
 while i <= xの平方根
  if xがiで割り切れる
   return false
  // 偶数はすでにチェックしているので、i + 2となる
  i = i + 2
  
 return true