ある時突然、「１３は素数ですか？」と質問されたとします。きっと皆さんはすぐに「素数です」と答えることができるでしょう。
それは１３が素数であるということを元から知っていたからかもしれませんし、13以下の素数「２，３，５，７，１１」で１３が割り切れないと瞬時に考えたからかもしれません。
では、コンピュータに「１３は素数？」と質問してみたときのコンピュータの考え方を紹介します。
コンピュータは素数の定義のみを知っているとします。（２や３が素数ということは教えていません）
私達なら13以下の素数のみ割り算を行えば良いとわかりますが、そもそもコンピュータは13以下の素数が何なのか分かっていないのでそれは不可能です。
では、どういう動きになるのでしょうか？
それは、１から順に１２まで割って行こうとします。
つまり……「13/1…13/2…13/3………13/12」というふうになります。
非効率的だと感じませんか？
ではここで２つアドバイスを上げましょう。もちろん「１３以下の素数で割る」というのは不可能です。
与えるアドバイスは「１３の平方根以下の自然数で順に割っていく」「２以上の自然数のみ考える。」の２つです。
少し複雑でしょうか？
具体的に考えてみましょう。１３の平方根は3.6…..ですので、「13の平方根以下の自然数」とは「１，２，３」となります。
さらに、「2以上の自然数のみ」ということになるので、2つのアドバイスにあった数は「２，３」のみになります。
つまり、2つのアドバイスを与えることでコンピュータは「13/2…13/3」を計算するだけで素数判定を行うことができるようになるのです。
たった2つ変えただけなのにかなりの手間が省けましたね。
なぜ13以下の平方根以下の自然数でいいのか？という疑問が浮かんだ人はいませんか？
それは平方数をこすと同じ数が出てくるからです。具体例をあげます（素数では難しいので１８を用います）
１８（平方根は大体4.2です）を二つの数の積で表していくと……「1×18,2×9,3×6」となります。4以上の数を考えると、既に出たものの順番を入れ替えただけになります。だから平方根以下の自然数のみ考えればよいのです。
実は、今回考えた手順の簡略化（計算の効率化）というのが「アルゴリズム研究」の基本的なものです。
アルゴリズムとは大雑把に言ってしまえばコンピュータを動かすための命令文のようなものです。これをいかに簡単にするか、というのがアルゴリズム研究です。
ちょっと方法を変えるだけでかなり効率的に素数を判定する事ができるようになりましたね。素数判定以外にも「最短経路問題」など身近なところに効率化を求めるようなものが有ります。気がついたときに少しだけ考えてみてはいかがでしょうか。数学の知恵が日常生活に役に立ってることを感じることができるのではないでしょうか。