Probability of Euler 's Totient Function in a range [L, R] to be divisible by M | Python3 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
size = 1000001 NEW_LINE def seiveOfEratosthenes ( prime ) : NEW_LINE INDENT prime [ 0 ] = 1 NEW_LINE prime [ 1 ] = 0 NEW_LINE i = 2 NEW_LINE while ( i * i < 1000001 ) : NEW_LINE INDENT if ( prime [ i ] == 0 ) : NEW_LINE INDENT j = i * i NEW_LINE while ( j < 1000001 ) : NEW_LINE INDENT prime [ j ] = 1 NEW_LINE j = j + i NEW_LINE DEDENT DEDENT i += 1 NEW_LINE DEDENT DEDENT def probabiltyEuler ( prime , L , R , M ) : NEW_LINE INDENT arr = [ 0 ] * size NEW_LINE eulerTotient = [ 0 ] * size NEW_LINE count = 0 NEW_LINE for i in range ( L , R + 1 ) : NEW_LINE INDENT eulerTotient [ i - L ] = i NEW_LINE arr [ i - L ] = i NEW_LINE DEDENT for i in range ( 2 , 1000001 ) : NEW_LINE INDENT if ( prime [ i ] == 0 ) : NEW_LINE INDENT for j in range ( ( L // i ) * i , R + 1 , i ) : NEW_LINE INDENT if ( j - L >= 0 ) : NEW_LINE INDENT eulerTotient [ j - L ] = ( eulerTotient [ j - L ] // i * ( i - 1 ) ) NEW_LINE while ( arr [ j - L ] % i == 0 ) : NEW_LINE INDENT arr [ j - L ] = arr [ j - L ] // i NEW_LINE DEDENT DEDENT DEDENT DEDENT DEDENT for i in range ( L , R + 1 ) : NEW_LINE INDENT if ( arr [ i - L ] > 1 ) : NEW_LINE INDENT eulerTotient [ i - L ] = ( ( eulerTotient [ i - L ] // arr [ i - L ] ) * ( arr [ i - L ] - 1 ) ) NEW_LINE DEDENT DEDENT for i in range ( L , R + 1 ) : NEW_LINE INDENT if ( ( eulerTotient [ i - L ] % M ) == 0 ) : NEW_LINE INDENT count += 1 NEW_LINE DEDENT DEDENT return ( float ) ( 1.0 * count / ( R + 1 - L ) ) NEW_LINE DEDENT prime = [ 0 ] * size NEW_LINE seiveOfEratosthenes ( prime ) NEW_LINE L , R , M = 1 , 7 , 3 NEW_LINE print ( probabiltyEuler ( prime , L , R , M ) ) NEW_LINE