Find sum of exponents of prime factors of numbers 1 to N | Function to implement sieve of erastosthenes ; Create a boolean array and initialize all entries as false ; Initializing smallest factor equal to 2 for all the even numbers ; Iterate for odd numbers less then equal to n ; s ( i ) for a prime is the number itself ; For all multiples of current prime number ; i is the smallest prime factor for number " i * j " ; Function to generate prime factors and its power ; s [ i ] is going to store smallest prime factor of i ; Current prime factor of N ; Power of current prime factor ; Calculating prime factors and their powers sum ; Increment the count and continue the process ; Add count to the sum ; Reinitialize count ; Return the result ; Function to find the sum of all the power of prime factors of N ; Iterate for in [ 2 , N ] ; Driver Code ; Given number N ; Function call
def sieveOfEratosthenes ( N , s ) : NEW_LINE INDENT prime = [ False ] * ( N + 1 ) NEW_LINE for i in range ( 2 , N + 1 , 2 ) : NEW_LINE INDENT s [ i ] = 2 NEW_LINE DEDENT for i in range ( 3 , N + 1 , 2 ) : NEW_LINE INDENT if ( prime [ i ] == False ) : NEW_LINE INDENT s [ i ] = i NEW_LINE j = i NEW_LINE while ( j * i <= N ) : NEW_LINE INDENT if ( prime [ i * j ] == False ) : NEW_LINE INDENT prime [ i * j ] = True NEW_LINE s [ i * j ] = i NEW_LINE DEDENT j += 2 NEW_LINE DEDENT DEDENT DEDENT DEDENT def generatePrimeFactors ( N ) : NEW_LINE INDENT s = [ 0 ] * ( N + 1 ) NEW_LINE sum = 0 NEW_LINE sieveOfEratosthenes ( N , s ) NEW_LINE curr = s [ N ] NEW_LINE cnt = 1 NEW_LINE while ( N > 1 ) : NEW_LINE INDENT N //= s [ N ] NEW_LINE if ( curr == s [ N ] ) : NEW_LINE INDENT cnt += 1 NEW_LINE continue NEW_LINE DEDENT sum = sum + cnt NEW_LINE curr = s [ N ] NEW_LINE cnt = 1 NEW_LINE DEDENT return sum NEW_LINE DEDENT def findSum ( N ) : NEW_LINE INDENT sum = 0 NEW_LINE for i in range ( 2 , N + 1 ) : NEW_LINE INDENT sum += generatePrimeFactors ( i ) NEW_LINE DEDENT print ( sum ) NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT N = 4 NEW_LINE findSum ( N ) NEW_LINE DEDENT