プロジェクトオイラー Problem 46 「もうひとつのゴールドバッハの予想」 †

Problem 46 「もうひとつのゴールドバッハの予想」 †

Christian Goldbachは全ての奇合成数は平方数の2倍と素数の和で表せると予想した.

9 = 7 + 2×12
15 = 7 + 2×22
21 = 3 + 2×32
25 = 7 + 2×32
27 = 19 + 2×22
33 = 31 + 2×12

後に, この予想は誤りであることが分かった.

平方数の2倍と素数の和で表せない最小の奇合成数はいくつか?

http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2046



解法
素数を篩にかけてあとは
上限値を定めて下から地道に計算するだけです。
上限値までで作れた数はok配列で作れたと記録します。
作れてない奇合成数に出会ったらそれが答え。
答えが出なかったら適当に上限値をあげていきます。

#include<stdio.h>
#include<string.h>

const int LIMIT=10000;

int main(){
      bool is_prime[LIMIT+1];
      int bigO=0;
      memset(is_prime,true,sizeof(is_prime));
      is_prime[0]=is_prime[1]=false;
      for(int i=2;i*i<=LIMIT;i++){
            if(is_prime[i]==false)continue;
            int start,add;
            if(i==2){
                  start=4;
                  add=2;
            }else{
                  start=i*i;
                  add=i*2;
            }
            for(int j=start;j<=LIMIT;j+=add){
                  bigO++;
                  is_prime[j]=false;
            }
      }
      int ans=0;
      bool ok[LIMIT];
      memset(ok,false,sizeof(ok));
      for(int i=3;i<=LIMIT;i+=2){
            if(ok[i]==false&&is_prime[i]==false){
                  ans=i;
                  break;
            }
            if(is_prime[i]==false)continue;
            for(int j=1;;j++){
                  int p=i+2*j*j;
                  if(p>LIMIT)break;
                  ok[p]=true;
                  bigO++;
            }
      }
      printf("ans=%d,bigO=%d\n",ans,bigO);
}