Find number of Coprimes with `N` given in a range.

general
, , ,
1

I have a range [L-R] 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] = p-1;
 
            for (int i = 2*p; i<=n; i += p)
            {
               phi[i] = (phi[i]/p) * (p-1);
            }
        }
    }
 
    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
2

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.

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

  2. 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.

3

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.

4

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.

5

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