TopCoder SRM 389 Div1 Easy

問題

ある整数の素因数が全てk以下であるとき、その数はk-smoothであるという。
与えられた整数N以下の正の整数のうちk-smoothであるものの数を求めよ。

制約条件

N≦200000
k≦200000

方針

1〜Nのboolの配列を作る。最初全てが1(候補である)。
kより大きい全ての素数について、その倍数を全て候補から消す。


これを行った後で、残っているのがk-smoothな数。

ソースコード

const int MX=100001;
bool p[MX],ng[MX];
class SmoothNumbers {
  public:
  int countSmoothNumbers(int N, int k) {
    memset(p,0,sizeof(p));
    memset(ng,0,sizeof(ng));
    for(int i=2;i*i<MX;i++)if(!p[i])for(int j=i*i;j<MX;j+=i)p[j]=1;
    int ans=N;
    for(int i=k+1;i<=N;i++)if(!p[i]){
      for(int j=i;j<=N;j+=i)if(!ng[j])ng[j]=1, ans--;
    }
    return ans;
  }
};