# Getting TLE

Problem Link :- KPRIME Problem - CodeChef

My Logic :- I have precomputed still getting TLE…

``````using namespace std;
using ll = long long;
int N = 10000000;
vector<int> sieve(N);

#define fast_io ios_base::sync_with_stdio(false); cin.tie(NULL);
#define MOD 1e9+7;

void init_code()
{
fast_io;
#ifndef ONLINE_JUDGE

freopen("input.txt", "r", stdin);

freopen("output.txt", "w", stdout);

#endif // ONLINE_JUDGE
}

void createsieve()
{

for(int i=1;i<=N;i++)
{
sieve[i] = i;
}

for(int i=2;i*i<=N;i++)
{
if(sieve[i] == i)
{
for(int j=i*i;j<=N;j+=i)
{
if(sieve[j] == j)
{
sieve[j] = i;
}
}
}
}
}

void solve()
{
int a,b,k;
cin>>a>>b>>k;

vector<int> ans;
int count = 0;
for(int i=a;i<=b;i++)
{
int x = i;

set<int> s;

while(x != 1)
{
s.insert(sieve[x]);
x = x/sieve[x];
}

if(s.size() == k)
{
count++;
}
}

cout<<count<<"\n";
}

int main()
{
init_code();
createsieve();

int t;
cin>>t;

while(t--)
{
solve();
}

return 0;
}`````````

Time complexity is O( T*(B-A)) , which in worst case would be 10^10 operation which will TLE , precalculate answer for x (1<=x<=100000) before answering the Test cases

Can u give me idea how can i precalculate x values

The same you are doing it for a to b , Just calculate count of no. Of prime factor for each no. from 1 to N , store it in an array , then create another array cnt[N][6] , where cnt[i][j] will store that how many no. between 1 and i have j prime factor , and then answer for each query will be cnt[b][k]-cnt [a-1][k]

1 Like

Implementation of @dhruv788’s approach:

``````using namespace std;

const ll N = 100001;
vector<ll> spf(N);
vector<vector<ll>> cnt_of_prime(N,vector<ll>(6,0));

void generate(){
for(ll i=0;i<N;i++) spf[i] = i;
for(ll i = 2;i*i<N;i++){
if(spf[i] == i){
for(ll j = i*i;j<N;j+=i){
if(spf[j]==j) spf[j] = i;
}
}
}
}
ll distinctPrime(ll a){
unordered_set<ll> st;
while(a!=1){
st.insert(spf[a]);
a = a/spf[a];
}
return st.size();
}
void generateResult(){
//cout<<Prime(10)<<"\n";
for(ll i = 2;i<N;i++){

for(int j = 0;j<6;j++){
cnt_of_prime[i][j] = cnt_of_prime[i-1][j];
}
ll cur = distinctPrime(i);
if(cur<6){
cnt_of_prime[i][cur]++;
}
}
}

void solve(){
ll a,b,k;cin>>a>>b>>k;
cout<<cnt_of_prime[b][k]-cnt_of_prime[a-1][k]<<"\n";
}

int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
generate();

generateResult();
TestCase
solve();
}
``````
1 Like

Your generate functiom is wrong , you should have done if ( spf[ j ]!=j) spf[j]=i; in the loop of j

1 Like

But I got AC
submission

Great ( Maybe that is what matters )

Yesss…

1 Like

Bro I have some small doubts

(i) why j < 6 only why not other number…
(ii) i did not get why needed 2d array

We need 2d array to keep the count of numbers having j distinct prime factors from [1, i] (that’s why we used 6 because numbers having distinct prime count >= 6 can be ignored according to problem constraints. i.e 1<=k<=5)

P.S think of it as a prefix sum array.

1 Like

Got it Bro . Thanks

1 Like