プロジェクトオイラー Problem 47 「異なる素因数」 †

Problem 47 「異なる素因数」 †

それぞれ2つの異なる素因数を持つ連続する2つの数が最初に現れるのは:

14 = 2 × 7
15 = 3 × 5

それぞれ3つの異なる素因数を持つ連続する3つの数が最初に現れるのは:

644 = 22 × 7 × 23
645 = 3 × 5 × 43
646 = 2 × 17 × 19

最初に現れるそれぞれ4つの異なる素因数を持つ連続する4つの数を求めよ. その最初の数はいくつか?

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

解法
素数を求める篩をすこし改造して
後は上限を定めて探索するだけです。
見つからなければ上限を増やします。

#include<stdio.h>

const int LIMIT=200000;

int main(){
      int prime_count[LIMIT+1]={0};
      int bigO=0;

      for(int i=2;i<=LIMIT;i++){
            if(prime_count[i]>0)continue;
            for(int j=i;j<=LIMIT;j+=i){
                  bigO++;
                  prime_count[j]++;
            }
      }
      int ans=0;
      for(int i=2;i<LIMIT-4;i++){
            if(prime_count[i]==4&&prime_count[i+1]==4&&
                  prime_count[i+2]==4&&prime_count[i+3]==4){
                  ans=i;
                  break;
            }
            bigO++;
      }
      printf("ans=%d bigO=%d\n",ans,bigO);
}