Probability of Euler 's Totient Function in a range [L, R] to be divisible by M | Java Program to implement the above approach ; Seieve of Erotosthenes to compute all primes ; If prime ; Mark all its multiples as non - prime ; Function to find the probability of Euler 's Totient Function in a given range ; Initializing two arrays with values from L to R for Euler 's totient ; Indexing from 0 ; If the current number is prime ; Checking if i is prime factor of numbers in range L to R ; Update all the numbers which has prime factor i ; If number in range has a prime factor > Math . sqrt ( number ) ; Count those which are divisible by M ; Return the result ; Driver Code
import java . util . * ; class GFG { static final int size = 1000001 ; static void seiveOfEratosthenes ( int [ ] prime ) { prime [ 0 ] = 1 ; prime [ 1 ] = 0 ; for ( int i = 2 ; i * i < 1000001 ; i ++ ) { if ( prime [ i ] == 0 ) { for ( int j = i * i ; j < 1000001 ; j += i ) { prime [ j ] = 1 ; } } } } static float probabiltyEuler ( int [ ] prime , int L , int R , int M ) { int [ ] arr = new int [ size ] ; int [ ] eulerTotient = new int [ size ] ; int count = 0 ; for ( int i = L ; i <= R ; i ++ ) { eulerTotient [ i - L ] = i ; arr [ i - L ] = i ; } for ( int i = 2 ; i < 1000001 ; i ++ ) { if ( prime [ i ] == 0 ) { for ( int j = ( L / i ) * i ; j <= R ; j += i ) { if ( j - L >= 0 ) { eulerTotient [ j - L ] = eulerTotient [ j - L ] / i * ( i - 1 ) ; while ( arr [ j - L ] % i == 0 ) { arr [ j - L ] /= i ; } } } } } 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 ++ ) { if ( ( eulerTotient [ i - L ] % M ) == 0 ) { count ++ ; } } return ( float ) ( 1.0 * count / ( R + 1 - L ) ) ; } 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 ) ) ; } }