Given three integers L, R, and M, the task is to find the probability of Euler’s Totient Function of a number in the range [L, R] is divisible by M.
Euler’s Totient function is the count of numbers in {1, 2, 3, …, N} that are relatively prime to N, i.e., the numbers whose GCD (Greatest Common Divisor) with N is 1.
Examples:
Input: L = 1, R = 5, M = 2
Output: 0.6
Explanation:
Euler’s Totient Function for N = 1, 2, 3, 4 and 5 is {1, 1, 2, 2, 4} respectively.
Count of Euler’s Totient Function divisible by M(= 2) is 3.
Therefore, the required probability is 3/5 = 0.6Input: L = 1, R = 7, M = 4
Output: 0.142
Explanation:
Euler’s Totient Function for N = 1, 2, 3, ….7 is {1, 1, 2, 2, 4, 2, 6} respectively.
Count of Euler’s Totient Function divisible by M(= 4) is 1.
Therefore, the required probability is 1/7 = 0.142
Approach: The idea is to pre-compute Euler’s Totient Function and iterate over the given range and count the numbers divisible by M to calculate the probability.
For the computation of the Euler’s Totient Function, use the Euler’s Product Formula :
where pi is the prime factor of N.
For every prime factor i of N ( L <= n <= R), perform the following steps:
- Subtract all multiples of i from [1, N].
- Update N by repeatedly dividing it by i.
- If the reduced N is more than 1, then remove all multiples of N from result.
For the computation of the prime factors, use Sieve of Eratosthenes method. The probability in the given range will be count/(L – R + 1).
Below is the implementation of the above approach:
C++
// C++ Program to implement // the above approach #include <bits/stdc++.h> using namespace std; #define size 1000001 // Seieve of Erotosthenes // to compute all primes void seiveOfEratosthenes( int * prime) { prime[0] = 1, prime[1] = 0; for ( int i = 2; i * i < 1000001; i++) { // If prime if (prime[i] == 0) { for ( int j = i * i; j < 1000001; j += i) { // Mark all its multiples // as non-prime prime[j] = 1; } } } } // Function to find the probability of // Euler's Totient Function in a given range float probabiltyEuler( int * prime, int L, int R, int M) { int * arr = new int [size]{ 0 }; int * eulerTotient = new int [size]{ 0 }; int count = 0; // Initializing two arrays // with values from L to R // for Euler's totient for ( int i = L; i <= R; i++) { // Indexing from 0 eulerTotient[i - L] = i; arr[i - L] = i; } for ( int i = 2; i < 1000001; i++) { // If the current number is prime if (prime[i] == 0) { // Checking if i is prime factor // of numbers in range L to R for ( int j = (L / i) * i; j <= R; j += i) { if (j - L >= 0) { // Update all the numbers // which has prime factor i eulerTotient[j - L] = eulerTotient[j - L] / i * (i - 1); while (arr[j - L] % i == 0) { arr[j - L] /= i; } } } } } // If number in range has a // prime factor > sqrt(number) for ( int i = L; i <= R; i++) { if (arr[i - L] > 1) { eulerTotient[i - L] = (eulerTotient[i - L] / arr[i - L]) * (arr[i - L] - 1); } } for ( int i = L; i <= R; i++) { // Count those which are divisible by M if ((eulerTotient[i - L] % M) == 0) { count++; } } // Return the result return (1.0 * count / (R + 1 - L)); } // Driver Code int main() { int * prime = new int [size]{ 0 }; seiveOfEratosthenes(prime); int L = 1, R = 7, M = 3; cout << probabiltyEuler(prime, L, R, M); return 0; } |
Java
// Java Program to implement // the above approach import java.util.*; class GFG{ static final int size = 1000001 ; // Seieve of Erotosthenes // to compute all primes static void seiveOfEratosthenes( int []prime) { prime[ 0 ] = 1 ; prime[ 1 ] = 0 ; for ( int i = 2 ; i * i < 1000001 ; i++) { // If prime if (prime[i] == 0 ) { for ( int j = i * i; j < 1000001 ; j += i) { // Mark all its multiples // as non-prime prime[j] = 1 ; } } } } // Function to find the probability of // Euler's Totient Function in a given range static float probabiltyEuler( int []prime, int L, int R, int M) { int [] arr = new int [size]; int []eulerTotient = new int [size]; int count = 0 ; // Initializing two arrays // with values from L to R // for Euler's totient for ( int i = L; i <= R; i++) { // Indexing from 0 eulerTotient[i - L] = i; arr[i - L] = i; } for ( int i = 2 ; i < 1000001 ; i++) { // If the current number is prime if (prime[i] == 0 ) { // Checking if i is prime factor // of numbers in range L to R for ( int j = (L / i) * i; j <= R; j += i) { if (j - L >= 0 ) { // Update all the numbers // which has prime factor i eulerTotient[j - L] = eulerTotient[j - L] / i * (i - 1 ); while (arr[j - L] % i == 0 ) { arr[j - L] /= i; } } } } } // If number in range has a // prime factor > Math.sqrt(number) for ( int i = L; i <= R; i++) { if (arr[i - L] > 1 ) { eulerTotient[i - L] = (eulerTotient[i - L] / arr[i - L]) * (arr[i - L] - 1 ); } } for ( int i = L; i <= R; i++) { // Count those which are divisible by M if ((eulerTotient[i - L] % M) == 0 ) { count++; } } // Return the result return ( float ) ( 1.0 * count / (R + 1 - L)); } // Driver Code public static void main(String[] args) { int []prime = new int [size]; seiveOfEratosthenes(prime); int L = 1 , R = 7 , M = 3 ; System.out.print(probabiltyEuler(prime, L, R, M)); } } // This code is contributed by sapnasingh4991 |
Python3
# Python3 program to implement # the above approach size = 1000001 # Seieve of Erotosthenes # to compute all primes def seiveOfEratosthenes(prime): prime[ 0 ] = 1 prime[ 1 ] = 0 i = 2 while (i * i < 1000001 ): # If prime if (prime[i] = = 0 ): j = i * i while (j < 1000001 ): # Mark all its multiples # as non-prime prime[j] = 1 j = j + i i + = 1 # Function to find the probability of # Euler's Totient Function in a given range def probabiltyEuler(prime, L, R, M): arr = [ 0 ] * size eulerTotient = [ 0 ] * size count = 0 # Initializing two arrays # with values from L to R # for Euler's totient for i in range (L, R + 1 ): # Indexing from 0 eulerTotient[i - L] = i arr[i - L] = i for i in range ( 2 , 1000001 ): # If the current number is prime if (prime[i] = = 0 ): # Checking if i is prime factor # of numbers in range L to R for j in range ((L / / i) * i, R + 1 , i): if (j - L > = 0 ): # Update all the numbers # which has prime factor i eulerTotient[j - L] = (eulerTotient[j - L] / / i * (i - 1 )) while (arr[j - L] % i = = 0 ): arr[j - L] = arr[j - L] / / i # If number in range has a # prime factor > Math.sqrt(number) for i in range (L, R + 1 ): if (arr[i - L] > 1 ): eulerTotient[i - L] = ((eulerTotient[i - L] / / arr[i - L]) * (arr[i - L] - 1 )) for i in range (L, R + 1 ): # Count those which are divisible by M if ((eulerTotient[i - L] % M) = = 0 ): count + = 1 # Return the result return ( float )( 1.0 * count / (R + 1 - L)) # Driver code prime = [ 0 ] * size seiveOfEratosthenes(prime) L, R, M = 1 , 7 , 3 print (probabiltyEuler(prime, L, R, M)) # This code is contributed by divyeshrabadiya07 |
C#
// C# Program to implement // the above approach using System; class GFG{ static readonly int size = 1000001; // Seieve of Erotosthenes // to compute all primes static void seiveOfEratosthenes( int []prime) { prime[0] = 1; prime[1] = 0; for ( int i = 2; i * i < 1000001; i++) { // If prime if (prime[i] == 0) { for ( int j = i * i; j < 1000001; j += i) { // Mark all its multiples // as non-prime prime[j] = 1; } } } } // Function to find the probability of // Euler's Totient Function in a given range static float probabiltyEuler( int []prime, int L, int R, int M) { int [] arr = new int [size]; int []eulerTotient = new int [size]; int count = 0; // Initializing two arrays // with values from L to R // for Euler's totient for ( int i = L; i <= R; i++) { // Indexing from 0 eulerTotient[i - L] = i; arr[i - L] = i; } for ( int i = 2; i < 1000001; i++) { // If the current number is prime if (prime[i] == 0) { // Checking if i is prime factor // of numbers in range L to R for ( int j = (L / i) * i; j <= R; j += i) { if (j - L >= 0) { // Update all the numbers // which has prime factor i eulerTotient[j - L] = eulerTotient[j - L] / i * (i - 1); while (arr[j - L] % i == 0) { arr[j - L] /= i; } } } } } // If number in range has a // prime factor > Math.Sqrt(number) for ( int i = L; i <= R; i++) { if (arr[i - L] > 1) { eulerTotient[i - L] = (eulerTotient[i - L] / arr[i - L]) * (arr[i - L] - 1); } } for ( int i = L; i <= R; i++) { // Count those which are divisible by M if ((eulerTotient[i - L] % M) == 0) { count++; } } // Return the result return ( float ) (1.0 * count / (R + 1 - L)); } // Driver Code public static void Main(String[] args) { int []prime = new int [size]; seiveOfEratosthenes(prime); int L = 1, R = 7, M = 3; Console.Write(probabiltyEuler(prime, L, R, M)); } } // This code is contributed by sapnasingh4991 |
Javascript
<script> // JavaScript Program to implement // the above approach let size = 1000001; let prime = new Array(size,0); // Seieve of Erotosthenes // to compute all primes function seiveOfEratosthenes() { prime[0] = 1; prime[1] = 0; for (let i = 2; i * i < 1000001; i++) { // If prime if (prime[i] == 0) { for (let j = i * i; j < 1000001; j += i) { // Mark all its multiples // as non-prime prime[j] = 1; } } } } // Function to find the probability of // Euler's Totient Function in a given range function probabiltyEuler(L,R, M) { let arr = new Array(size,0); let eulerTotient = new Array(size,0); let count = 0; // Initializing two arrays // with values from L to R // for Euler's totient for (let i = L; i <= R; i++) { // Indexing from 0 eulerTotient[i - L] = i; arr[i - L] = i; } for (let i = 2; i < 1000001; i++) { // If the current number is prime if (prime[i] == 0) { // Checking if i is prime factor // of numbers in range L to R for (let j = (L / i) * i; j <= R; j += i) { if (j - L >= 0) { // Update all the numbers // which has prime factor i eulerTotient[j - L] = eulerTotient[j - L] / i * (i - 1); while (arr[j - L] % i == 0) { arr[j - L] /= i; } } } } } // If number in range has a // prime factor > Math.Sqrt(number) for (let i = L; i <= R; i++) { if (arr[i - L] > 1) { eulerTotient[i - L] = (eulerTotient[i - L] / arr[i - L]) * (arr[i - L] - 1); } } for (let i = L; i <= R; i++) { // Count those which are divisible by M if ((eulerTotient[i - L] % M) == 0) { count++; } } count/=2; // Return the result return 1.0 * count / (R + 1 - L); } // Driver Code seiveOfEratosthenes(); let L = 1; let R = 7; let M = 3; document.write(probabiltyEuler(L, R, M).toFixed(7)); </script> |
0.142857
Time Complexity : O(Nlog(N))
Auxiliary Space: O(size), where size denotes the number upto which Sieve is calculated.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!