Sum of Maximum and Minimum prime factor of every number in the Array | Python3 implementation of the approach ; max_prime [ i ] represent maximum prime number that divides the number i ; min_prime [ i ] represent minimum prime number that divides the number i ; Function to store the minimum prime factor and the maximum prime factor in two arrays ; Check for prime number if min_prime [ i ] > 0 , then it is not a prime number ; if i is a prime number min_prime number that divide prime number and max_prime number that divide prime number is the number itself . ; If this number is being visited for first time then this divisor must be the smallest prime number that divides this number ; The last prime number that divides this number will be maximum . ; Function to find the sum of the minimum and the maximum prime factors of every number from the given array ; Pre - calculation ; For every element of the given array ; The sum of its smallest and largest prime factor ; Driver code
MAX = 100000 NEW_LINE max_prime = [ 0 ] * ( MAX + 1 ) NEW_LINE min_prime = [ 0 ] * ( MAX + 1 ) NEW_LINE def sieve ( n ) : NEW_LINE INDENT for i in range ( 2 , n + 1 ) : NEW_LINE INDENT if ( min_prime [ i ] > 0 ) : NEW_LINE INDENT continue NEW_LINE DEDENT min_prime [ i ] = i NEW_LINE max_prime [ i ] = i NEW_LINE j = i + i NEW_LINE while ( j <= n ) : NEW_LINE INDENT if ( min_prime [ j ] == 0 ) : NEW_LINE INDENT min_prime [ j ] = i NEW_LINE DEDENT max_prime [ j ] = i NEW_LINE j += i NEW_LINE DEDENT DEDENT DEDENT def findSum ( arr , n ) : NEW_LINE INDENT sieve ( MAX ) NEW_LINE for i in range ( n ) : NEW_LINE INDENT sum = min_prime [ arr [ i ] ] + max_prime [ arr [ i ] ] NEW_LINE print ( sum , end = " ▁ " ) NEW_LINE DEDENT DEDENT arr = [ 5 , 10 , 15 , 20 , 25 , 30 ] NEW_LINE n = len ( arr ) NEW_LINE findSum ( arr , n ) NEW_LINE