問題
http://community.topcoder.com/stat?c=problem_statement&pm=8519&rd=11122
解き方
あらかじめ対象となる全ての数について素数かどうか判定しておけば
O(sqrt(10^5) * 10^5)=O(3*10^7)なので間に合う。
素数かどうかの判定にエラトステネスのふるいを使えば
こちらの計算量も多く見積もってsqrt(10^5)*5*10^4=1.5*10^7程度。
コード
int isprime[100001];
class SmoothNumbers {
public: int countSmoothNumbers(int N, int k) {
FORE(i,0,100001)isprime[i]=1;
isprime[0]=0,isprime[1]=0;
for(int i=2;i*i<=100000;i++)if(isprime[i]){
for(int j=i*2;j<=100000;j+=i)isprime[j]=0;
}
int ret=0;
for(int i=1;i<=N;i++){
int mx=0;
for(int j=2;j*j<=i;j++)if(i%j==0){
if(isprime[j])mx=max(mx,j);
if(isprime[i/j])mx=max(mx,i/j);
}
if(isprime[i])mx=i;
if(mx<=k)ret++;
}
return ret;
}
};
class SmoothNumbers {
public: int countSmoothNumbers(int N, int k) {
FORE(i,0,100001)isprime[i]=1;
isprime[0]=0,isprime[1]=0;
for(int i=2;i*i<=100000;i++)if(isprime[i]){
for(int j=i*2;j<=100000;j+=i)isprime[j]=0;
}
int ret=0;
for(int i=1;i<=N;i++){
int mx=0;
for(int j=2;j*j<=i;j++)if(i%j==0){
if(isprime[j])mx=max(mx,j);
if(isprime[i/j])mx=max(mx,i/j);
}
if(isprime[i])mx=i;
if(mx<=k)ret++;
}
return ret;
}
};