### rum3r's blog

By rum3r, history, 4 weeks ago,

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;
}
}

}


PROBLEM

• -4

 » 4 weeks ago, # | ← Rev. 2 →   0 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]
•  » » 4 weeks ago, # ^ |   0 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??
•  » » » 4 weeks ago, # ^ |   0 bro check your question k is up to 5 only constraint..
•  » » » » 4 weeks ago, # ^ |   0 Thanks!! You really helped a lot!
•  » » » » 4 weeks ago, # ^ |   0 Bro I got AC. 0.01s? Can you tell me complexity? How it's blazing fast?? AC I swear this is the last one :)