Minimize the cost to split a number | Python3 implementation of the approach ; check if a number is prime or not ; run a loop upto square root of x ; Function to return the minimized cost ; If n is prime ; If n is odd and can be split into ( prime + 2 ) then cost will be 1 + 1 = 2 ; Every non - prime even number can be expressed as the sum of two primes ; n is odd so n can be split into ( 3 + even ) further even part can be split into ( prime + prime ) ( 3 + prime + prime ) will cost 3 ; Driver code
from math import sqrt NEW_LINE def isPrime ( x ) : NEW_LINE INDENT for i in range ( 2 , int ( sqrt ( x ) ) + 1 ) : NEW_LINE INDENT if ( x % i == 0 ) : NEW_LINE INDENT return 0 ; NEW_LINE DEDENT DEDENT return 1 ; NEW_LINE DEDENT def minimumCost ( n ) : NEW_LINE INDENT if ( isPrime ( n ) ) : NEW_LINE INDENT return 1 ; NEW_LINE DEDENT if ( n % 2 == 1 and isPrime ( n - 2 ) ) : NEW_LINE INDENT return 2 ; NEW_LINE DEDENT if ( n % 2 == 0 ) : NEW_LINE INDENT return 2 ; NEW_LINE DEDENT return 3 ; NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT n = 6 ; NEW_LINE print ( minimumCost ( n ) ) ; NEW_LINE DEDENT