# HackerRank Problem ("Leonardo's Prime Factors")

It is throwing run time error for testcase 11 ,16 and 17;
Otherwise its run fine .
Below is my code

#include <bits/stdc++.h>
#define ll long long int
#define MAX 50
int prime[MAX];
#include<vector>
using namespace std;
vector<ll> allp;
vector<ll> qa;
void findprime()
{
for(ll i=0;i<MAX;i++)
prime[i]=1;
prime[0]=0;
prime[1]=0;
for(ll i=2;i<MAX;i++)
{
if(prime[i]==0)
continue;
for(ll j=i*i;j<MAX;j+=i)
prime[j]=0;
}
for(ll i=0;i<MAX;i++)
{
if(prime[i]==1)
allp.push_back(i);
}

}

/*
* Complete the primeCount function below.
*/
int primeCount(long n) {
ll ans=0;
ll k=0;
ll x=1;
while(n/allp[k]>0)
{
n/=allp[k++];
ans++;
}
return ans;
}

int main()
{
ofstream fout(getenv("OUTPUT_PATH"));
findprime();
int q;
cin >> q;
cin.ignore(numeric_limits<streamsize>::max(), '\n');

for (int q_itr = 0; q_itr < q; q_itr++) {
long n;
cin >> n;
cin.ignore(numeric_limits<streamsize>::max(), '\n');

int result = primeCount(n);

fout << result << "\n";
}

fout.close();

return 0;
}


I think the problem is with the parameter â€ślongâ€ť as the number can go upto 10^18 so u should try with long long â€¦maybe it will work out.

The problem is with your logic, just use a little common sense and see what is actually happening. In the problem itself, they have given a big hint when explaining the test-case when n = 500.

I donâ€™t think you need to use Sieve of Eratosthenes for generating prime in your function void findprime(), you can use O(\sqrt{n}) algorithm for it as the upper bound for prime need not be 50 it is much lower.

UPD-1:
I solved it using a different approach, if you want you can have a look.
My Solution Link: Competitive-Programming/Hacker-Rank/Leonardo-Prime-Factors at master Â· strikersps/Competitive-Programming Â· GitHub

1 Like

#define MAX 60 will fix it.

1 Like

I already tried with long longâ€¦

I use it only for first 20 prime . I think it will not affect much more â€¦

You are rightâ€¦ @everule1
But can you tell me how you think and find this mistake?

And why itâ€™s failing for 50 ?
At max we require only first 17 or 19 prime even though i extend this MAX to 50 â€¦so why itâ€™s failing on even 50 also?

Can you explain briefly what your primeCount() function is doing?

In fact, youâ€™re right. The largest prime possible is 47. However, you are not taking into account the possibility of an out of bounds access. If 47 is allowed, the next value you check will be out of bounds, thus giving a runtime error.