SmoothNumbers.cpp

class SmoothNumbers {
    public:
    //sieve
    int countSmoothNumbers(int N, int k) {
        vector<bool> isPrime(N+1, true);
        vector<int> largestPF(N+1, 1);
        long long i, j; //LL
        for(i=2;i<=N;++i){
            if(isPrime[i]){
                largestPF[i]=i;
                for(j=2;i*j<=N;++j){
                    isPrime[i*j]=false;
                    largestPF[i*j]=i;
                }
            }
        }

        int ans=1;
        for(int i=2;i<=N;++i) if(largestPF[i]<=k) ans++;
        return ans;
    }


        //brute force
    int countSmoothNumbers1(int N, int k) {
        int ans=N;
        for(int i=1;i<=N;++i){
            int x=i;
            for(int j=2;j<=k;++j){
                while(x%j==0) x/=j;
            }
            if(x>1) ans--;
        }
        return ans;
    }
};