TopCoder SRM 389 Div1 Easy
問題
ある整数の素因数が全てk以下であるとき、その数はk-smoothであるという。
与えられた整数N以下の正の整数のうちk-smoothであるものの数を求めよ。
制約条件
N≦200000
k≦200000
ソースコード
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; } };