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;
}
2 Likes
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.
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.
In know At that time (4 yr) this wont help you
For those Like me who come here will see it helpful
My approach :
n → take prime factorisation
Now we have to delete the factors of all the primes that comes in Factorisation of n
(x/p) number of factor of p in [1…x]
{p1 , p2 ,p3 ,p4 …} be the prime factorisation of n
x/p1 + x/p2 + x/p3 …
but there are some repeatation  x/(p1p2)  x/(p2p3)
By mobius (Inclusion Exclusion Principle)
(p1p2p3…) odd time then sign is ve and otherwise +
Finally : iterate over subsets of primes that comes in factorisation
take p = product of elements in the subset
x/p → be the factors of that
sign of it is taken in to count that size of subset is odd or even