Count numbers in a given range whose count of prime factors is a Prime Number | Python3 program to implement the above approach ; Function to find the smallest prime factor of all the numbers in range [ 0 , MAX ] ; Stores smallest prime factor of all the numbers in the range [ 0 , MAX ] ; No smallest prime factor of 0 and 1 exists ; Traverse all the numbers in the range [ 1 , MAX ] ; Update spf [ i ] ; Update all the numbers whose smallest prime factor is 2 ; Traverse all the numbers in the range [ 1 , sqrt ( MAX ) ] ; Check if i is a prime number ; Update all the numbers whose smallest prime factor is i ; Check if j is a prime number ; Function to find count of prime factor of num ; Stores count of prime factor of num ; Calculate count of prime factor ; Update count ; Update num ; Function to precalculate the count of numbers in the range [ 0 , i ] whose count of prime factors is a prime number ; Stores the sum of all the numbers in the range [ 0 , i ] count of prime factor is a prime number ; Traverse all the numbers in the range [ 1 , MAX ] ; Stores count of prime factor of i ; If count of prime factor is a prime number ; Update sum [ i ] ; Update sum [ i ] ; Driver code ; Stores smallest prime factor of all the numbers in the range [ 0 , MAX ] ; Stores the sum of all the numbers in the range [ 0 , i ] count of prime factor is a prime number ; N = sizeof ( Q ) / sizeof ( Q [ 0 ] ) ;
MAX = 1001 NEW_LINE def sieve ( ) : NEW_LINE INDENT global MAX NEW_LINE spf = [ 0 ] * MAX NEW_LINE spf [ 0 ] = spf [ 1 ] = - 1 NEW_LINE for i in range ( 2 , MAX ) : NEW_LINE INDENT spf [ i ] = i NEW_LINE DEDENT for i in range ( 4 , MAX , 2 ) : NEW_LINE INDENT spf [ i ] = 2 NEW_LINE DEDENT for i in range ( 3 , MAX ) : NEW_LINE INDENT if ( spf [ i ] == i ) : NEW_LINE INDENT for j in range ( i * i , MAX ) : NEW_LINE INDENT if ( spf [ j ] == j ) : NEW_LINE INDENT spf [ j ] = i NEW_LINE DEDENT DEDENT DEDENT DEDENT return spf NEW_LINE DEDENT def countFactors ( spf , num ) : NEW_LINE INDENT count = 0 NEW_LINE while ( num > 1 ) : NEW_LINE INDENT count += 1 NEW_LINE num = num // spf [ num ] NEW_LINE DEDENT return count NEW_LINE DEDENT def precalculateSum ( spf ) : NEW_LINE INDENT sum = [ 0 ] * MAX NEW_LINE for i in range ( 1 , MAX ) : NEW_LINE INDENT prime_factor = countFactors ( spf , i ) NEW_LINE if ( spf [ prime_factor ] == prime_factor ) : NEW_LINE INDENT sum [ i ] = sum [ i - 1 ] + 1 NEW_LINE DEDENT else : NEW_LINE INDENT sum [ i ] = sum [ i - 1 ] NEW_LINE DEDENT DEDENT return sum NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT spf = sieve ( ) NEW_LINE sum = precalculateSum ( spf ) NEW_LINE Q = [ [ 4 , 8 ] , [ 30 , 32 ] ] NEW_LINE sum [ Q [ 0 ] [ 1 ] ] += 1 NEW_LINE for i in range ( 0 , 2 ) : NEW_LINE INDENT print ( ( sum [ Q [ i ] [ 1 ] ] - sum [ Q [ i ] [ 0 ] ] ) , end = " ▁ " ) NEW_LINE DEDENT DEDENT