Find four factors of N with maximum product and sum equal to N | Set 3 | Python3 implementation of above approach ; Function to find primes ; Corner cases ; This is checked so that we can skip middle five numbers in below loop ; Function to find factors ; run a loop upto square root of that number ; if the n is perfect square ; otherwise push it 's two divisors ; sort the divisors ; Function to find max product ; To store factors of 'n ; find factors ; if it is divisible by 4. ; if it is prime ; otherwise answer will be possible ; include last third factor ; nested loop to find other two factors ; Driver code ; function call
from math import sqrt , ceil , floor NEW_LINE def isPrime ( n ) : NEW_LINE INDENT if ( n <= 1 ) : NEW_LINE INDENT return False NEW_LINE DEDENT if ( n <= 3 ) : NEW_LINE INDENT return True NEW_LINE DEDENT if ( n % 2 == 0 or n % 3 == 0 ) : NEW_LINE INDENT return False NEW_LINE DEDENT for i in range ( 5 , ceil ( sqrt ( n ) ) , 6 ) : NEW_LINE INDENT if ( n % i == 0 or n % ( i + 2 ) == 0 ) : NEW_LINE INDENT return False NEW_LINE DEDENT DEDENT return True NEW_LINE DEDENT def factors ( N , v ) : NEW_LINE INDENT for i in range ( 2 , N ) : NEW_LINE INDENT for j in range ( 1 , ceil ( sqrt ( i ) ) + 1 ) : NEW_LINE INDENT if ( i % j == 0 ) : NEW_LINE INDENT if ( i // j == j ) : NEW_LINE INDENT v [ i ] . append ( j ) NEW_LINE DEDENT else : NEW_LINE INDENT v [ i ] . append ( j ) NEW_LINE v [ i ] . append ( i // j ) NEW_LINE DEDENT DEDENT DEDENT v = sorted ( v ) NEW_LINE DEDENT DEDENT def product ( n ) : NEW_LINE ' NEW_LINE INDENT v = [ [ ] ] * ( n + 100 ) NEW_LINE factors ( n + 100 , v ) NEW_LINE if ( n % 4 == 0 ) : NEW_LINE INDENT x = n // 4 NEW_LINE x *= x NEW_LINE return x * x NEW_LINE DEDENT else : NEW_LINE INDENT if ( isPrime [ n ] ) : NEW_LINE INDENT return - 1 NEW_LINE DEDENT else : NEW_LINE INDENT ans = - 1 NEW_LINE if ( len ( v [ n ] ) > 2 ) : NEW_LINE INDENT fac = v [ n ] [ len ( v [ n ] ) - 3 ] NEW_LINE for i in range ( len ( v [ n ] - 1 ) , - 1 , - 1 ) : NEW_LINE INDENT for j in range ( len ( v [ n ] - 1 ) , - 1 , - 1 ) : NEW_LINE INDENT if ( ( fac * 2 ) + ( v [ n ] [ j ] + v [ n ] [ i ] ) == n ) : NEW_LINE INDENT ans = max ( ans , fac * fac * v [ n ] [ j ] * v [ n ] [ i ] ) NEW_LINE DEDENT DEDENT DEDENT return ans NEW_LINE DEDENT DEDENT DEDENT DEDENT n = 24 NEW_LINE print ( product ( n ) ) NEW_LINE