Project Euler で紹介されている問題35を解いてみました。条件を満たす素数を求めていく問題です。
Project Euler 問題35（循環素数）
数字 197 は、197、971、および 719 のすべての（左）回転して得られる数字が素数であるため、循環素数と呼ばれます。
100 未満の循環素数は、2、3、5、7、11、13、17、31、37、71、73、79、97 の 13 個あります。
100万未満の循環素数の個数を求めよ。
考察
素数であるか判定する関数 is_prime は、道具箱から引用します。
判定する関数 is_satisfied は、以下の順番で判定します。
- 判定する数字の桁数を求める。
- 判定する数字が素数か判定する。
- 一桁ずつ左回転して、素数か判定する。
- すべての場合に、素数であれば、1 を返す。それ以外の場合に 0 を返す。
解答例
考察した is_satisfied は、一桁の数字でも動作します。1 以上100万未満の自然数に対して条件を満たす自然数の個数をカウントします。
全体の C プログラムは、以下となります。
#include <stdio.h>
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 is_satisfied(int number)
{
int ret_val = 1;
int original, digits;
int i, mask, rotate_number, temp_digit;
original = number;
digits = 0;
while (number > 0) {
++digits;
number = number / 10;
}
mask = 10;
for (i = 2; i <= digits; ++i) {
mask = mask * 10;
}
if (is_prime(original) == 0) {
ret_val = 0;
}
rotate_number = original;
for (i = 1; i < digits; ++i) {
rotate_number = rotate_number * 10;
temp_digit = rotate_number / mask;
rotate_number = rotate_number % mask + temp_digit;
if (is_prime(rotate_number) == 0) {
ret_val = 0;
break;
}
}
return ret_val;
}
int main(void)
{
int n;
int count = 0;
for (n = 1; n < 1000000; ++n) {
if (is_satisfied(n) == 1) {
// printf("%d\n", n);
++count;
}
}
printf("Problem035: %d\n", count);
return 0;
}コメントした行（65行目）を有効にすれば、条件を満たす数を出力します。
上記のプログラムの計算量は、それほど大きくはなく、一瞬で解答を求めることができています。
最後に
計算機を使ってある条件を満たす素数を求める問題は、いろいろなバリエーションがあります。プログラミングを通じて、素数の不思議さを感じることできました。
引き続き、Project Euler の問題を紹介していきます。
