Probability of Euler 's Totient Function in a range [L, R] to be divisible by M | JavaScript 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
let size = 1000001 ; let prime = new Array ( size , 0 ) ; function seiveOfEratosthenes ( ) { prime [ 0 ] = 1 ; prime [ 1 ] = 0 ; for ( let i = 2 ; i * i < 1000001 ; i ++ ) { if ( prime [ i ] == 0 ) { for ( let j = i * i ; j < 1000001 ; j += i ) { prime [ j ] = 1 ; } } } } function probabiltyEuler ( L , R , M ) { let arr = new Array ( size , 0 ) ; let eulerTotient = new Array ( size , 0 ) ; let count = 0 ; for ( let i = L ; i <= R ; i ++ ) { eulerTotient [ i - L ] = i ; arr [ i - L ] = i ; } for ( let i = 2 ; i < 1000001 ; i ++ ) { if ( prime [ i ] == 0 ) { for ( let 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 ( 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 ++ ) { if ( ( eulerTotient [ i - L ] % M ) == 0 ) { count ++ ; } } count /= 2 ; return 1.0 * count / ( R + 1 - L ) ; } seiveOfEratosthenes ( ) ; let L = 1 ; let R = 7 ; let M = 3 ; document . write ( probabiltyEuler ( L , R , M ) . toFixed ( 7 ) ) ;