Given three integers N, L, and R. The task is to calculate the number of natural numbers in the range [L, R] (both inclusive) which are relatively prime with N.
Examples:
Input: N = 10, L = 1, R = 25
Output: 10
Explanation:
10 natural numbers (in the range 1 to 25) are relatively prime to 10.
They are 1, 3, 7, 9, 11, 13, 17, 19, 21, 23.Input: N = 12, L = 7, R = 38
Output: 11
Explanation:
11 natural numbers (in the range 1 to 38) are relatively prime to 12.
They are 7, 11, 13, 17, 19, 23, 25, 29, 31, 35, 37.
Approach:
- At first, factorize the number N. Thus, find out all the prime factors of N.
- Store prime factors of the number N in an array.
- We can determine the total number of natural numbers which are not greater than R and are divisible by prime factors of N.
- Suppose that the value is y. So, exactly y natural numbers not greater than R have at least a single common divisor with N.
- So, these y numbers can not be relatively prime to N.
- Thus, the number of natural number not greater than R which are relatively prime to N will be R – y .
- Now, similarly we need to find out the number of relatively prime numbers of N which are not greater than L-1.
- Then, subtract the result for L-1 from the answer for R.
Below is the implementation of the above approach:
C++
// C++ code to count of natural// numbers in range [L, R] which// are relatively prime with N#include <bits/stdc++.h>using namespace std;#define maxN (long long)1000000000000// container of all the primes// up to sqrt(n)vector<int> prime;// Function to calculate prime// factors of nvoid sieve(long long n){ // run the sieve of Eratosthenes bool check[1000007] = { 0 }; long long i, j; // 0(false) means prime, // 1(true) means not prime check[0] = 1, check[1] = 1, check[2] = 0; // no even number is // prime except for 2 for (i = 4; i <= n; i += 2) check[i] = true; for (i = 3; i * i <= n; i += 2) if (!check[i]) { // all the multiples of each // each prime numbers are // non-prime for (j = i * i; j <= n; j += 2 * i) check[j] = true; } prime.push_back(2); // get all the primes // in prime vector for (int i = 3; i <= n; i += 2) if (!check[i]) prime.push_back(i); return;}// Count the number of numbers// up to m which are divisible// by given prime numberslong long count(long long a[], int n, long long m){ long long parity[3] = { 0 }; // Run from i= 000..0 to i= 111..1 // or check all possible // subsets of the array 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]; // take the multiplication // of all the set bits // if the number of set bits // is odd, then add to the // number of multiples parity[__builtin_popcount(i) & 1] += (m / mult); } return parity[1] - parity[0];}// Function calculates all number// not greater than 'm' which are// relatively prime with n.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 square of the prime number // is greater than 'n', it can't // be a factor of 'n' if ((long long)prime[i] * (long long)prime[i] > n) break; // if prime is a factor of // n then increment count 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 << "\n";}// Driver codeint main(){ long long N = 7, L = 3, R = 9; countRelPrimeInRange(N, L, R); return 0;} |
Java
// Java code to count of natural// numbers in range [L, R] which// are relatively prime with Nimport java.util.*;class GFG{static int maxN = 100000000;// Container of all the primes// up to sqrt(n)static Vector<Integer> prime = new Vector<Integer>();// Function to calculate prime// factors of nstatic void sieve(int n){ // Run the sieve of Eratosthenes boolean[] check = new boolean[1000007]; for(int i = 0; i < 1000007; i++) check[i] = false; int i, j; // 0(false) means prime, // 1(true) means not prime check[0] = false; check[1] = true; check[2] = false; // No even number is // prime except for 2 for(i = 4; i <= n; i += 2) check[i] = true; for(i = 3; i * i <= n; i += 2) if (!check[i]) { // All the multiples of each // each prime numbers are // non-prime for(j = i * i; j <= n; j += 2 * i) check[j] = true; } prime.add(2); // Get all the primes // in prime vector for(i = 3; i <= n; i += 2) if (!check[i]) prime.add(i); return;}static int countSetBits(int n){ int count = 0; while (n > 0) { count += n & 1; n >>= 1; } return count;}// Count the number of numbers// up to m which are divisible// by given prime numbersstatic int count(int a[], int n, int m){ int[] parity = new int[3]; for(int i = 0; i < 3; i++) parity[i] = 0; // Run from i= 000..0 to i= 111..1 // or check all possible // subsets of the array for(int i = 1; i < (1 << n); i++) { int mult = 1; for(int j = 0; j < n; j++) if ((i & (1 << j)) != 0) mult *= a[j]; // Take the multiplication // of all the set bits // If the number of set bits // is odd, then add to the // number of multiples parity[countSetBits(i) & 1] += (m / mult); } return parity[1] - parity[0];}// Function calculates all number// not greater than 'm' which are// relatively prime with n.static int countRelPrime(int n, int m){ int[] a = new int[20]; int i = 0, j = 0; int pz = prime.size(); while(n != 1 && i < pz) { // If square of the prime number // is greater than 'n', it can't // be a factor of 'n' if ((int)prime.get(i) * (int)prime.get(i) > n) break; // If prime is a factor of // n then increment count if (n % prime.get(i) == 0) { a[j] = (int)prime.get(i); j++; } while (n % prime.get(i) == 0) n /= prime.get(i); i++; } if (n != 1) { a[j] = n; j++; } return m - count(a, j, m);}static void countRelPrimeInRange(int n, int l, int r){ sieve((int)Math.sqrt(maxN)); int result = countRelPrime(n, r) - countRelPrime(n, l - 1); System.out.println(result);}// Driver codepublic static void main(String[] args){ int N = 7, L = 3, R = 9; countRelPrimeInRange(N, L, R);}}// This code is contributed by grand_master |
Python3
# Python3 code to count of natural# numbers in range [L, R] which# are relatively prime with Nfrom math import sqrt, floormaxN = 1000000000000# Container of all the primes# up to sqrt(n)prime = []# Function to calculate prime# factors of ndef sieve(n): # Run the sieve of Eratosthenes check = [0] * (1000007) i, j = 0, 0 # 0(false) means prime, # 1(True) means not prime check[0] = 1 check[1] = 1 check[2] = 0 # No even number is # prime except for 2 for i in range(4, n + 1, 2): check[i] = True for i in range(3, n + 1, 2): if i * i > n: break if (not check[i]): # All the multiples of each # each prime numbers are # non-prime for j in range(2 * i, n + 1, 2 * i): check[j] = True prime.append(2) # Get all the primes # in prime vector for i in range(3, n + 1, 2): if (not check[i]): prime.append(i) return# Count the number of numbers# up to m which are divisible# by given prime numbersdef count(a, n, m): parity = [0] * 3 # Run from i = 000..0 to i = 111..1 # or check all possible # subsets of the array for i in range(1, 1 << n): mult = 1 for j in range(n): if (i & (1 << j)): mult *= a[j] # Take the multiplication # of all the set bits # If the number of set bits # is odd, then add to the # number of multiples parity[bin(i).count('1') & 1] += (m // mult) return parity[1] - parity[0]# Function calculates all number# not greater than 'm' which are# relatively prime with n.def countRelPrime(n, m): a = [0] * 20 i = 0 j = 0 pz = len(prime) while (n != 1 and i < pz): # If square of the prime number # is greater than 'n', it can't # be a factor of 'n' if (prime[i] * prime[i] > n): break # If prime is a factor of # n then increment count if (n % prime[i] == 0): a[j] = prime[i] j += 1 while (n % prime[i] == 0): n //= prime[i] i += 1 if (n != 1): a[j] = n j += 1 return m - count(a, j, m)def countRelPrimeInRange(n, l, r): sieve(floor(sqrt(maxN))) result = (countRelPrime(n, r) - countRelPrime(n, l - 1)) print(result)# Driver codeif __name__ == '__main__': N = 7 L = 3 R = 9 countRelPrimeInRange(N, L, R)# This code is contributed by mohit kumar 29 |
C#
// C# code to count of natural// numbers in range [L, R] which// are relatively prime with Nusing System;using System.Collections.Generic;class GFG{ static int maxN = 100000000;// Container of all the primes// up to sqrt(n)static List<int> prime = new List<int>(); // Function to calculate prime// factors of nstatic void sieve(int n){ // Run the sieve of Eratosthenes bool[] check = new bool[1000007]; for(int I = 0; I < 1000007; I++) check[I] = false; int i, j; // 0(false) means prime, // 1(true) means not prime check[0] = false; check[1] = true; check[2] = false; // No even number is // prime except for 2 for(i = 4; i <= n; i += 2) check[i] = true; for(i = 3; i * i <= n; i += 2) if (!check[i]) { // All the multiples of each // each prime numbers are // non-prime for(j = i * i; j <= n; j += 2 * i) check[j] = true; } prime.Add(2); // Get all the primes // in prime vector for(i = 3; i <= n; i += 2) if (!check[i]) prime.Add(i); return;} static int countSetBits(int n){ int count = 0; while (n > 0) { count += n & 1; n >>= 1; } return count;} // Count the number of numbers// up to m which are divisible// by given prime numbersstatic int count(int[] a, int n, int m){ int[] parity = new int[3]; for(int i = 0; i < 3; i++) parity[i] = 0; // Run from i= 000..0 to i= 111..1 // or check all possible // subsets of the array for(int i = 1; i < (1 << n); i++) { int mult = 1; for(int j = 0; j < n; j++) if ((i & (1 << j)) != 0) mult *= a[j]; // Take the multiplication // of all the set bits // If the number of set bits // is odd, then add to the // number of multiples parity[countSetBits(i) & 1] += (m / mult); } return parity[1] - parity[0];} // Function calculates all number// not greater than 'm' which are// relatively prime with n.static int countRelPrime(int n, int m){ int[] a = new int[20]; int i = 0, j = 0; int pz = prime.Count; while (n != 1 && i < pz) { // If square of the prime number // is greater than 'n', it can't // be a factor of 'n' if ((int)prime[i] * (int)prime[i] > n) break; // If prime is a factor of // n then increment count if (n % prime[i] == 0) { a[j] = (int)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);} static void countRelPrimeInRange(int n, int l, int r){ sieve((int)Math.Sqrt(maxN)); int result = countRelPrime(n, r) - countRelPrime(n, l - 1); Console.WriteLine(result);}// Driver Codestatic void Main() { int N = 7, L = 3, R = 9; countRelPrimeInRange(N, L, R);}}// This code is contributed by divyeshrabadiya07 |
Javascript
<script>// Javascript code to count of natural// numbers in range [L, R] which// are relatively prime with Nlet maxN = 100000000;// Container of all the primes// up to sqrt(n)let prime = [];// Function to calculate prime// factors of nfunction sieve(n){ // Run the sieve of Eratosthenes let check = new Array(1000007); for(let i = 0; i < 1000007; i++) check[i] = false; let i, j; // 0(false) means prime, // 1(true) means not prime check[0] = false; check[1] = true; check[2] = false; // No even number is // prime except for 2 for(i = 4; i <= n; i += 2) check[i] = true; for(i = 3; i * i <= n; i += 2) if (!check[i]) { // All the multiples of each // each prime numbers are // non-prime for(j = i * i; j <= n; j += 2 * i) check[j] = true; } prime.push(2); // Get all the primes // in prime vector for(i = 3; i <= n; i += 2) if (!check[i]) prime.push(i); return;}function countSetBits(n){ let count = 0; while (n > 0) { count += n & 1; n >>= 1; } return count;}// Count the number of numbers// up to m which are divisible// by given prime numbersfunction count(a, n, m){ let parity = new Array(3); for(let i = 0; i < 3; i++) parity[i] = 0; // Run from i= 000..0 to i= 111..1 // or check all possible // subsets of the array for(let i = 1; i < (1 << n); i++) { let mult = 1; for(let j = 0; j < n; j++) if ((i & (1 << j)) != 0) mult *= a[j]; // Take the multiplication // of all the set bits // If the number of set bits // is odd, then add to the // number of multiples parity[countSetBits(i) & 1] += (m / mult); } return parity[1] - parity[0];}// Function calculates all number// not greater than 'm' which are// relatively prime with n.function countRelPrime(n, m){ let a = new Array(20); let i = 0, j = 0; let pz = prime.length; while(n != 1 && i < pz) { // If square of the prime number // is greater than 'n', it can't // be a factor of 'n' if (prime[i] * prime[i] > n) break; // If prime is a factor of // n then increment count if (n % prime[i] == 0) { a[j] = prime[i]; j++; } while (n % prime[i] == 0) n = Math.floor(n/prime[i]); i++; } if (n != 1) { a[j] = n; j++; } return m - count(a, j, m);}function countRelPrimeInRange(n, l, r){ sieve(Math.floor(Math.sqrt(maxN))); let result = countRelPrime(n, r) - countRelPrime(n, l - 1); document.write(result);}// Driver codelet N = 7, L = 3, R = 9;countRelPrimeInRange(N, L, R);// This code is contributed by unknown2108</script> |
Output:
6
Time Complexity: O(2^N * log(R))
Auxiliary Space: O(N + maxN)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
