https://www.codechef.com/LRNDSA07/problems/KPRIME

help
1

My code is giving TLE can anyone optimize my code.

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define vi vector<int>
#define ff first
#define ss second
#define ins insert
#define endl "\n"
#define pie_op ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define tc int t;cin>>t;while(t--)
#define pb push_back

const int MOD=1e9+7;

vi pr(100001, 0);
int dp[6][100001]={0};

void seive(){
	for(int i=1;i<=100000;i++){
		int n=i;
		for(int j=2;j<=n;j++){
			if(n%j==0){
    			while(n%j==0)
	    			n/=j;
	    			
	    		pr[i]=1+pr[n];	
	    		n=1;
	    		break;
			}	
		}
		if(n>1){
			pr[i]=1;
		}
	}
	for(int i=1;i<=100000;i++){
		for(int j=1;j<=5;j++){
			if(pr[i]==j){
				dp[j][i]=dp[j][i-1]+1;
			}
			else
			    dp[j][i]=dp[j][i-1];
		}
	}
}

int main()
{
	pie_op;
	seive();
	tc{
		int ans=0;
		int a,b,k;cin>>a>>b>>k;
		cout<<dp[k][b]-dp[k][a-1]<<endl;
	}
    return 0;
}
2

Change the code to calculate the number of unique prime factors of a number.

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
const int nax = 2e6 + 9;
const int MOD = 1e9 + 7;
int prime[nax];
void sieve() {
   for (int i = 2; i < nax; ++i) {
      if(prime[i] > 0) continue;
      for (int j = 2; (i * j) < nax; ++j)
         ++prime[i * j];
   }
}
void inline test_cases() {
   int A, B, K, res = 0;
   cin >> A >> B >> K;
   for (int i = A; i <= B; ++i)
      if(prime[i] == K) ++res;

   cout << res << endl;
}

signed main() {
   ios_base::sync_with_stdio(false);
   cin.tie(NULL);
   // #ifndef ONLINE_JUDGE
   //    freopen("input.txt", "r", stdin);
   // #endif
   sieve();
   int t = 1;
   // cin >> t;
   while(t--) {
      test_cases();
   }
   return 0;
}

while running the sieve, you can mark the prime factor of each number.

3

it is not getting accepted. and i think this will also give TLE

4

I just submitted the code.
https://www.codechef.com/viewsolution/45739460

5

ohhh sorry …my bad… thanks