I have a range [LR] and I have to find out the number of coprimes with another integer N
within the range.
The issue is that N varies from 1 <= N <= 10^9, and L,R varies from 1 <= L <= R <= 10^18.
I was thinking of using Euler’s Totient method, however I dont know how to implement it. Moreover, for values of N near 10^7, it runs for very long, and ultimately gives me a TLE.
Here’s my code.
#include<iostream>
using namespace std;
void computeTotient(int n)
{
long phi[n+1];
for (int i=1; i<=n; i++)
phi[i] = i;
for (int p=2; p<=n; p++)
{
if (phi[p] == p)
{
phi[p] = p1;
for (int i = 2*p; i<=n; i += p)
{
phi[i] = (phi[i]/p) * (p1);
}
}
}
for (int i=1; i<=n; i++)
cout << "Totient of " << i << " is "
<< phi[i] << endl;
}
int main()
{
int n = 1000000000;
computeTotient(n);
return 0;
}
May i ask which problem this question refers to (link)
I possibly have a solution and would like to test it first.
I would also like to check if it isn’t part of a currently running contest before hinting at my solution.
I was asked this question in a Placement Interview Challenge at my college. I even tried searching this on Google, but couldn’t find a viable solution (which doesn’t gives a TLE). From basic number theory I was able to say that if we count the number of coprimes from the range (1, N) we can find the rest because for a number which, say X, belongs to (N, R), if X%N is a coprime, then X is a coprime as well. H The interviewers said I was going towards the right direction, but said this logic would be time consuming.
Unfortunately I am unable to test my solution then. Because figuring out a solution is more satisfying than just knowing it, I’ll give you two subproblems to guide you.

Write a function that generates all divisors of N with the following condition: the divisor isn’t divisible by a square number.

Write a function that takes 3 variables: L,R,N and returns the number of values in the range [L,R] that are divisible by n. Ranges of the variables are the same as in your problem. This function should have an efficiency of O(1)
I hope this helps. There is one step left to solve the problem: how to combine these two subproblems. For now, I’ll leave that up to you.
Note: my solution is far removed from your approach, but that doesn’t mean your approach can’t lead to an answer that also solves the problem.