Count numbers from a given range having exactly 5 distinct factors | Python3 implementation of the above approach ; Stores all prime numbers up to 2 * 10 ^ 5 ; Function to generate all prime numbers up to 2 * 10 ^ 5 using Sieve of Eratosthenes ; Mark 0 and 1 as non - prime ; If i is prime ; Mark all its factors as non - prime ; If current number is prime ; Store the prime ; Function to count numbers in the range [ L , R ] having exactly 5 factors ; Stores the required count ; Driver Code
N = 2 * 100000 NEW_LINE prime = [ 0 ] * N NEW_LINE def Sieve ( ) : NEW_LINE INDENT p = [ True ] * ( N + 1 ) NEW_LINE p [ 0 ] = p [ 1 ] = False NEW_LINE i = 2 NEW_LINE while ( i * i <= N ) : NEW_LINE INDENT if ( p [ i ] == True ) : NEW_LINE INDENT for j in range ( i * i , N , i ) : NEW_LINE INDENT p [ j ] = False NEW_LINE DEDENT DEDENT i += 1 NEW_LINE DEDENT for i in range ( N ) : NEW_LINE INDENT if ( p [ i ] != False ) : NEW_LINE INDENT prime . append ( pow ( i , 4 ) ) NEW_LINE DEDENT DEDENT DEDENT def countNumbers ( L , R ) : NEW_LINE INDENT Count = 0 NEW_LINE for p in prime : NEW_LINE INDENT if ( p >= L and p <= R ) : NEW_LINE INDENT Count += 1 NEW_LINE DEDENT DEDENT print ( Count ) NEW_LINE DEDENT L = 16 NEW_LINE R = 85000 NEW_LINE Sieve ( ) NEW_LINE countNumbers ( L , R ) NEW_LINE