Count of triplets having sum of product of any two numbers with the third number equal to N | C ++ program for the above approach ; 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 ; Find the SPF [ i ] ; Function Call
#include <bits/stdc++.h> NEW_LINE using namespace std ; vector < int > s ( 11 , 0 ) ; void sieveOfEratosthenes ( int N ) { bool prime [ N + 1 ] ; memset ( prime , false , sizeof ( false ) ) ; for ( int i = 2 ; i < N + 1 ; i += 2 ) s [ i ] = 2 ; for ( int i = 3 ; i < N + 1 ; i += 2 ) { if ( prime [ i ] == false ) { s [ i ] = i ; for ( int j = i ; j < N / i + 1 ; j += 2 ) { if ( prime [ i * j ] == false ) { prime [ i * j ] = true ; s [ i * j ] = i ; } } } } } int generatePrimeFactors ( int N ) { int curr = s [ N ] ; map < int , int > cnt ; cnt [ s [ N ] ] = 1 ; while ( N > 1 ) { N /= s [ N ] ; if ( N and s [ N ] ) if ( cnt . find ( s [ N ] ) == cnt . end ( ) ) cnt [ s [ N ] ] = 1 ; else cnt [ s [ N ] ] += 1 ; } if ( cnt . find ( 0 ) != cnt . end ( ) ) cnt . erase ( 0 ) ; int totfactor = 1 ; for ( auto i : cnt ) totfactor *= i . second + 1 ; return totfactor ; } int countTriplets ( int N ) { int CountTriplet = 0 ; for ( int z = 1 ; z < N + 1 ; z ++ ) { int p = generatePrimeFactors ( N - z ) ; if ( p > 1 ) CountTriplet += p ; } return CountTriplet + 1 ; } int main ( ) { int N = 10 ; sieveOfEratosthenes ( N ) ; cout << countTriplets ( N ) ; }