朝日新聞2004年7月17日のパズルパーク問題(�W)

問題

4桁の数字があり，隣り合う数字の差は全て1となる。そのうち素数となるものを求める。

解答への道(ヒント)

予め10000までの素数を求める。

数字を1桁ずつ取り出しa,b,c,dに割り当て，以下のような判定関数を作成する。

YesNo checknum( int n)
{
  if( n < 1000) return NO; // 4桁限定
  int a = ( n / 1000) % 10;
  int b = ( n / 100 ) % 10;
  int c = ( n / 10  ) % 10;
  int d = ( n / 1   ) % 10;
  if( abs(a-b) == 1 && abs(b-c) == 1 && abs(c-d) == 1) return YES; // 隣り合う数の差分が1
  return    NO;
}

素数は，数も小さいし，エラトステネス（EratosthenIs）の篩(ふるい)を使って求める。エラトステネスの篩いは以下のような感じ。

#define MAXPRIME 10000
  byte s[MAXPRIME]; // 1:素数, 0:素数でない
  for( int i=0; i< MAXPRIME; i++) {
    if( i&1) s[i] = 1; // 奇数は素数になる可能性がある
    else s[i] = 0; // 偶数は素数にならない
  }
  // 素数でない物を除く。
  s[0] = 0;
  s[1] = 0;
  s[2] = 1;
  for( i=3; i< MAXPRIME; i+=2) { // 奇数だけ調べる
    if( s[i]) {
      // 素数が見つかった。
      // 倍数を除去する。
      for( int j=i*2; j< MAXPRIME; j+=i) {
        s[j] = 0;
      }
    }
  }

解速度

即