Count of natural numbers in range [ L , R ] which are relatively prime with N | C ++ code to count of natural numbers in range [ L , R ] which are relatively prime with N ; container of all the primes up to sqrt ( n ) ; Function to calculate prime factors of n ; run the sieve of Eratosthenes ; 0 ( false ) means prime , 1 ( true ) means not prime ; no even number is prime except for 2 ; all the multiples of each each prime numbers are non - prime ; get all the primes in prime vector ; Count the number of numbers up to m which are divisible by given prime numbers ; Run from i = 000. . 0 to i = 111. . 1 or check all possible subsets of the array ; if the number of set bits is odd , then add to the number of multiples ; Function calculates all number not greater than ' m ' which are relatively prime with n . ; if square of the prime number is greater than ' n ' , it can ' t ▁ ▁ be ▁ a ▁ factor ▁ of ▁ ' n ' ; if prime is a factor of n then increment count ; Driver code
#include <bits/stdc++.h> NEW_LINE using namespace std ; #define maxN  (long long)1000000000000 NEW_LINE vector < int > prime ; void sieve ( long long n ) { bool check [ 1000007 ] = { 0 } ; long long i , j ; check [ 0 ] = 1 , check [ 1 ] = 1 , check [ 2 ] = 0 ; for ( i = 4 ; i <= n ; i += 2 ) check [ i ] = true ; for ( i = 3 ; i * i <= n ; i += 2 ) if ( ! check [ i ] ) { for ( j = i * i ; j <= n ; j += 2 * i ) check [ j ] = true ; } prime . push_back ( 2 ) ; for ( int i = 3 ; i <= n ; i += 2 ) if ( ! check [ i ] ) prime . push_back ( i ) ; return ; } long long count ( long long a [ ] , int n , long long m ) { long long parity [ 3 ] = { 0 } ; for ( int i = 1 ; i < ( 1 << n ) ; i ++ ) { long long mult = 1 ; for ( int j = 0 ; j < n ; j ++ ) if ( i & ( 1 << j ) ) mult *= a [ j ] ; parity [ __builtin_popcount ( i ) & 1 ] += ( m / mult ) ; } return parity [ 1 ] - parity [ 0 ] ; } long long countRelPrime ( long long n , long long m ) { long long a [ 20 ] ; int i = 0 , j = 0 ; long long pz = prime . size ( ) ; while ( n != 1 && i < pz ) { if ( ( long long ) prime [ i ] * ( long long ) prime [ i ] > n ) break ; if ( n % prime [ i ] == 0 ) a [ j ] = ( long long ) prime [ i ] , j ++ ; while ( n % prime [ i ] == 0 ) n /= prime [ i ] ; i ++ ; } if ( n != 1 ) a [ j ] = n , j ++ ; return m - count ( a , j , m ) ; } void countRelPrimeInRange ( long long n , long long l , long long r ) { sieve ( sqrt ( maxN ) ) ; long long result = countRelPrime ( n , r ) - countRelPrime ( n , l - 1 ) ; cout << result << " STRNEWLINE " ; } int main ( ) { long long N = 7 , L = 3 , R = 9 ; countRelPrimeInRange ( N , L , R ) ; return 0 ; }