**Can anyone share their approach who had solved the problem?
**
PROBLEM STATEMENT:
Henry is a curious little boy. He likes to play around with numbers.One day, he defined a
function f for natural numbers such that:
f(X) = largest prime factor of X , where X > 1
For example: f(2) = 2
f(3) = 3
f(75) = 5
Now, Henry selected two integers A and B (A ≤ B) and counted all numbers X between A and B (both inclusive) such that f(X) = K. He found out that there are N such numbers.
After that Henry went for playing. When he returned home, he found out that he had forgotten
the upper limit of range i.e. the integer B. However, he remembers all other numbers i.e. A, K
and N.
Henry wants to find out B as soon as possible. Can you help him finding it? Note:
If there are multiple possible values of B, output the least value out of those.
It is assured that the input will be in such a way that final value of B will be within the
range of long long int.
Input
First line of input contains T, the number of test cases.
The only line of each test case contains three integers A, K and N.
Output
For each test case, output a single line containing the integer B.
@srd091 i was getting runtime error in chefandsister while my code was running without error on my machine
my code### #include #include
#include<string.h>
using namespace std;
//long long int sum,t,a[100005],n,i,j,c;
long long int a[27],i,t,k,ans,n;
//char m1[100005],m2[100005],a[100005];
int main()
{
char str[27];
cin>>t;
while(t–)
{
cin>>str;
cin>>k;
For Henry, just generate all possible numbers whose Greatest Prime Factor is K using dfs and are less then (1 << 63)- 1, and store them in a array, then using binary search we can easily find the answer.
The total count of numbers whose prime factor is K would be quite low as for K = 11, it’d be around (200000), so it won’t result in TLE at all.
@vardhi you have specified length of char array str as 27 but input can be upto 50 char long, that may be the reason the you are getting run time error.
The point is to quickly calculate all the numbers that have greatest prime factor = K, and then to quickly answer the queries. For example If I have all the numbers for K = 11, and the A = 1e9 and N = 9999, then using binary search, I can find the lower bound for A in those numbers, suppose the index of lowerBound for A in the list of numbers is idx, then the lowest B’s index would be idx + n - 1 in the array.
the lowest number who greatest prime factor is K is K itself. So run dfs from K. Now all the other numbers would be it’s multiple from (2K, 3K, …(K^2)), so now number run dfs from the following numbers. Use map to keep track of the visited ones. Just be careful to check the overflow cases.