Project Euler で紹介されている問題37を解いてみました。左からまたは右から桁を消し続けても素数になる数を求める問題です。
Project Euler 問題37（切り捨て可能素数）
3797 という数字には興味深い性質があります。 それ自体が素数であることに加えて、数字を左から右に削除し、各段階で素数を得ることができます：3797、797、97、および 7。同様に、右から左に削除しても素数を得ることができます： 3797、379、37、および 3 です。
左から右へも右から左へも切り捨て可能な素数は 11 個ある。その素数の合計を求めよ。
注: 2、3、5、および 7 は、切り捨て可能な素数と考えません。
考察
素数であるか判定する関数 is_prime は、道具箱から引用します。
判定する関数 is_satisfied は、以下の順番で判定します。問題35と似たような構造になります。
- 判定する数字の桁数を求める。
- 判定する数字の左桁を消していき素数か判定する。
- 判定する数字の右桁を消していき素数か判定する。
- すべての場合に、素数であれば、1 を返す。それ以外の場合に 0 を返す。
解答例
10 以上100万未満の自然数に対して条件を満たす自然数の合計を求めます。
全体の C プログラムは、以下となります。
#include <stdio.h>
int is_prime(int n)
{
int answer = 1;
int i;
if (n <= 1) {
answer = 0;
}
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, check_number;
original = number;
digits = 0;
while (number > 0) {
++digits;
number = number / 10;
}
mask = 1;
for (i = 2; i <= digits; ++i) {
mask = mask * 10;
}
if (is_prime(original) == 0) {
ret_val = 0;
}
check_number = original % mask;
while (mask >= 10) {
if (is_prime(check_number) == 0) {
ret_val = 0;
break;
}
mask = mask / 10;
check_number = original % mask;
}
check_number = original / 10;
while (check_number > 0) {
if (is_prime(check_number) == 0) {
ret_val = 0;
break;
}
check_number = check_number / 10;
}
return ret_val;
}
int main(void)
{
int n, sum;
sum = 0;
for (n = 10; n < 1000000; ++n) {
if (is_satisfied(n) == 1) {
// printf("%d\n", n);
sum += n;
}
}
printf("Problem037: %d\n", sum);
return 0;
}コメントした行（73行目）を有効にすれば、条件を満たす数を出力します。
73行目をコメントアウトしたところ、問題文にあるように11個の素数が出力されました。条件を満たす一番大きな素数は、739397 でした。合計の数は、Project Euler のサイトで正解と判定されました。
最後に
単純に100万まで計算して、条件を満たす素数が11個あることしか分かっていません。739397 より大きな条件を満たす素数はないのか十分な検証ができていません。
次回は、上記が成立するのか考察します。
