Please Help Me

please help me
my code is given TLE
Question Link

My Code:
#define lli long long int
#define fast ios_base::sync_with_stdio(0);cin.tie(0);
#define vi vector
#define pb push_back
using namespace std;
lli present(lli n,lli k)
lli cnt=0;
for(lli i=1;i<=n;i++)
return cnt;
int main()
lli t;
lli n,k;

You are running a loop of size N to factorize a number N.

There are T=1000 test cases.
Complexity of your solution is O(T*N) which is huge.

You can use better factorization algorithms:
For example, Instead of checking all numbers till N, you can check till square root of N. That will give a O(T*sqrt(N)) solution which should be enough to pass.

1 Like

Thank u

1 Like

Instead of running loop from 1 to n u can run from 1 to sqrt(n) and then check if n is divisible by i as well as n/i increment by 2 else divisible only by 1 of i or n/i then increment by 1. Also give a condition that i!=n/i

1 Like