Cananyone explain me the DP solution of this problem??

### Why we are using DP? Why this solution isn't giving correct Answer?

###

#### What's the complexity of the solution that I have written I know for sieve it's O(N*log(logN)). But I have modified that.

```
const int maxN = 2e5 + 9;
bool prime[maxN];
int cnt[maxN];
void sieve(){
for(int i=2; i<=maxN; ++i){
prime[i] = 1;
cnt[i] = 0;
}
prime[0] = prime[1] = 0;
for(ll i=2; i*i<=maxN; ++i){
if(prime[i]){
cnt[i] = 1;
//incrementing all the multiples of primes by 1..
for(int j=2*i; j<=maxN; j+=i){
// dbg3(i, j, cnt[j]);
prime[j] = 0;
cnt[j]++;
}
}
}
//incrementing all primes after root N by 1..
for(int i=sqrt(maxN); i<=maxN; ++i){
if(prime[i]){
cnt[i] =1;
}
}
}
```

we are using dp because then for various test cases we did not need to transverse from a to b to count number having k primes..

we can compute an array by modification in sieve at once then we can maintain a dp[n][k] where k=1,2,3,4,5 ex. dp[n][1]=count of 1 primes up to n ... dp[n][2]=count of 2 primes up to n ..

then we can simply take difference of k primes up to b and a-1 that is dp[b][k]-dp[a-1][k]

Your explanation is quite helpful. Appreciate the effort!

Is there any mathematical proof for this that a number can only have 5 prime divisors atmost??

bro check your question

k is up to 5 only constraint..

Thanks!! You really helped a lot!

Bro I got AC. 0.01s? Can you tell me complexity? How it's blazing fast?? AC I swear this is the last one :)