Project Euler で紹介されている問題7を解いてみました。素直に素数を判定していく方法と、素数表を作りながら求める方法を紹介します。
問題7（10001番目の素数）
最初の6個の素数を並べる：2, 3, 5, 7, 11, 13、これから6番目の素数は13だとわかる。
10001番目の素数を求めよ。
解答例
素朴なやり方ですが、2から素数か判定していき、10001番目の素数を表示する、という方法を紹介します。関数 is_prime は、問題5で作ったものを再利用します。求める素数がそれほど大きくないので、短い時間で計算ができます。C での記述例を示します。
#include <stdio.h>
#include <limits.h> /* INT_MAX */
#define N 10001
int is_prime(int n)
{
int answer = 1;
int i;
if (n == 1) {
answer = 0; /* 1 is not a prime number. */
}
for (i = 2; i * i <= n; ++i) {
if (n % i == 0) {
answer = 0;
break;
}
}
return answer;
}
int main(void)
{
int answer;
int i;
int n_of_prime = 0;
for (i = 2; i <= INT_MAX; ++i) {
if (is_prime(i) == 1) {
++n_of_prime;
if (n_of_prime == N) {
answer = i;
break;
}
}
}
printf("Problem007: %d\n", answer);
return 0;
}変数名の補足ですが、n_of_prime は、number of prime（numbers）の意味です。
解答例（改善版）
まだ求める素数が小さいため、上記のプログラムでも計算時間はそれほどかかりません。一方、is_prime で、本来であれば素数で割り切れるかだけを確認すれば十分なのですが、$\sqrt{n}$ 以下の自然数すべてで割り切れるか確認しています。
素数表を作りながら、次の素数を求める改善版を示します。この改善版は素数表（素数だけを含む配列）を作りながら、素数判定する場合に、それまでに作成した素数表を使います。
このプログラムは、「改訂新版 C言語によるアルゴリズム事典」（奥村晴彦著 技術評論社 1991年）の「素数」の項を参考にしました。
#include <stdio.h>
#define N 10001
int prime[N];
void generate_primes(void)
{
int j, k, x;
prime[0] = 2;
x = 1;
k = 1;
while (k < N) {
x += 2;
j = 0;
while ((j < k)&&(x % prime[j] != 0)) {
++j;
}
if (j == k) {
prime[k] = x;
++k;
}
}
}
int main(void)
{
generate_primes();
printf("Problem007: %d\n", prime[10000]);
return 0;
}最後に
素数表を作る場合、エラトステネスの篩（ふるい）がよく知られていますが、問題10で紹介することにします。素数に関しては、計算機を使って興味深いことが確認できる場合も多く、これからも取り上げていくつもりです。
引き続き、Project Euler の問題を紹介していきます。
