Count of triplets having sum of product of any two numbers with the third number equal to N | Function to find the SPF [ i ] using the Sieve Of Erastothenes ; Stores whether i is prime or not ; Initializing smallest factor as 2 for all even numbers ; Iterate for all odd numbers < N ; SPF of i for a prime is the number itself ; Iterate for all the multiples of the current prime number ; The value i is smallest prime factor for i * j ; Function to generate prime factors and its power ; Current prime factor of N ; Stores the powers of the current prime factor ; Find all the prime factors and their powers ; Return the total count of factors ; Function to count the number of triplets satisfying the given criteria ; Stores the count of resultant triplets ; Add the count all factors of N - z to the variable CountTriplet ; Return total count of triplets ; Driver Code ; S [ i ] stores the smallest prime factor for each element i ; Find the SPF [ i ] ; 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 for j in range ( i , int ( N / i ) + 1 , 2 ) : NEW_LINE INDENT if ( prime [ i * j ] == False ) : NEW_LINE INDENT prime [ i * j ] = True NEW_LINE s [ i * j ] = i NEW_LINE DEDENT DEDENT DEDENT DEDENT DEDENT def generatePrimeFactors ( N ) : NEW_LINE INDENT curr = s [ N ] NEW_LINE cnt = { s [ N ] : 1 } NEW_LINE while ( N > 1 ) : NEW_LINE INDENT N //= s [ N ] NEW_LINE if N and s [ N ] : NEW_LINE INDENT if cnt . get ( s [ N ] , 0 ) == 0 : NEW_LINE INDENT cnt [ s [ N ] ] = 1 NEW_LINE DEDENT else : NEW_LINE INDENT cnt [ s [ N ] ] += 1 NEW_LINE DEDENT DEDENT DEDENT if 0 in cnt : NEW_LINE INDENT cnt . pop ( 0 ) NEW_LINE DEDENT totfactor = 1 NEW_LINE for i in cnt . values ( ) : NEW_LINE INDENT totfactor *= i + 1 NEW_LINE DEDENT return totfactor NEW_LINE DEDENT def countTriplets ( N ) : NEW_LINE INDENT CountTriplet = 0 NEW_LINE for z in range ( 1 , N + 1 ) : NEW_LINE INDENT p = generatePrimeFactors ( N - z ) NEW_LINE if p > 1 : NEW_LINE INDENT CountTriplet += p NEW_LINE DEDENT DEDENT return CountTriplet + 1 NEW_LINE DEDENT N = 10 NEW_LINE s = [ 0 ] * ( N + 1 ) NEW_LINE sieveOfEratosthenes ( N , s ) NEW_LINE print ( countTriplets ( N ) ) NEW_LINE