競技プログラミング

解法

まず、1から$10^7$までの数を順番に調べていくプログラムを考えます。
このとき、毎回素数かどうか判定するためには、その数までの数で割り切れるかどうかを調べる必要があるので、数字 n に対しては約 $\sqrt{n}$ 回の計算が必要です。
そこで、「エラトステネスの篩」というアルゴリズムを用いることで、素数かどうかを高速に判定することができます。
エラトステネスの篩とは、最初に数列を用意し、そのうちの素数を順番に取り出して、その倍数のうち自分以外をすべて取り除くという操作を繰り返すことで、素数を求めるアルゴリズムです。
これにより、毎回の判定にかかる計算の回数を 1 回に抑えることができます。
ただし、$n$ の倍数を取り除く操作には $\frac{10^7}{n}$ 回の計算が必要となります。
しかし、素数の個数は少ないため、$n$までの素数を求めるのに必要な計算の回数はだいたい $n \log \log n$ 回となります。
これに $10^7$ を代入すると、大体 $4 \times 10^7$ となり、$10^8$ より小さいので 1 秒以内に計算できます。

例

100までの素数を求めるときのエラトステネスの篩の動きを考えます。
まず、100までの数列を用意します。
次に、2を取り出して、2以外の2の倍数をすべて取り除きます。
そうすると、2, 3, 5, 7, 9, ... と奇数のみが残りますが、次に小さい3を取り出して、3以外の3の倍数をすべて取り除きます。
そうすると、2, 3, 5, 7, 11, ... が残ります。今度は5に対して同じ操作を行えばよいです。
これを繰り返すと、2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97 が残ります。
これが100までの素数です。
下の画像は、上の枠に数字、下の枠にその数字が消された倍数を示しています。
（はみ出ている際は、スクロールしてご覧ください。）