Sum of largest prime factor of each number less than equal to n | function to find sum of largest prime factor of each number less than equal to n ; Create an integer array " prime [ 0 . . n ] " and initialize all entries of it as 0. A value in prime [ i ] will finally be 0 if ' i ' is a prime , else it will contain the largest prime factor of ' i ' . ; If prime [ p ] is '0' , then it is a prime number ; Update all multiples of p ; Sum up the largest prime factor of all the numbers ; if ' p ' is a non - prime number then prime [ p ] gives its largesr prime factor ; ' p ' is a prime number ; required sum ; Driver code to test above function
def sumOfLargePrimeFactor ( n ) : NEW_LINE INDENT prime = [ 0 ] * ( n + 1 ) NEW_LINE sum = 0 NEW_LINE max = int ( n / 2 ) NEW_LINE for p in range ( 2 , max + 1 ) : NEW_LINE INDENT if prime [ p ] == 0 : NEW_LINE INDENT for i in range ( p * 2 , n + 1 , p ) : NEW_LINE INDENT prime [ i ] = p NEW_LINE DEDENT DEDENT DEDENT for p in range ( 2 , n + 1 ) : NEW_LINE INDENT if prime [ p ] : NEW_LINE INDENT sum += prime [ p ] NEW_LINE DEDENT else : NEW_LINE INDENT sum += p NEW_LINE DEDENT DEDENT return sum NEW_LINE DEDENT n = 12 NEW_LINE print ( " Sum ▁ = " , sumOfLargePrimeFactor ( n ) ) NEW_LINE