TLE in KPRIME

Someone please help me optimizing the approach in this problem

my code is here

//Program to print all prime factors of a given number n

#include "stdio.h"
#include "set"
#include "math.h"
using namespace std;


int inline inp()
{
    int n=0;
    char c=getchar_unlocked();
    while(c < '0' || c >'9') {c=getchar_unlocked();}
    while(c>='0' && c<='9')
    {
        n=(n<<3)+(n<<1)+c-'0';
        c=getchar_unlocked();
    }
    return n;
}


int pfactor(int n)
{
	set<int> s;
	int i;
	//while n is divisible by 2,print 2 and divide by 2
	while(n%2 == 0)
	{
		s.insert(2);
		n = n/2;
	}

	//n must be odd at this point
	//so we can skip one element  i.e i += 2
	for (i = 3; i < sqrt(n); i+=2)
	{
		//while i divides n, print i, and divide n by i
		while(n%i == 0)
		{
			s.insert(i);
			n = n/i;
		}
	}
	//if n is greater than 2, it is prime,print n
	if(n>2)
		s.insert(n);

	return s.size();
}

int main()
{
	int t,a,b,k,i,count;
	t = inp();
	while(t--)
	{
		count = 0;
		a=inp();
		b = inp();
		k = inp();
		for (i = a; i <= b; ++i)
		{
			if(pfactor(i) == k)
			count++;
		}
		printf("%d\n",count );
	}
	
	return 0;
}

Hello,

Please refer to the editorial for a detailed description about what you need to do in order to get AC…

Your idea is correct but you need to do some pre-calculations (that is, calculations before reading input). It is often known as pre-computing or memoizing the values :slight_smile:

Good luck,

Bruno

2 Likes
//