Count of triplets having sum of product of any two numbers with the third number equal to N | Java 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
import java . util . * ; class GFG { static int [ ] s = new int [ 11 ] ; static void sieveOfEratosthenes ( int N ) { boolean [ ] prime = new boolean [ N + 1 ] ; 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 ; } } } } } static int generatePrimeFactors ( int N ) { int curr = s [ N ] ; HashMap < Integer , Integer > cnt = new HashMap < > ( ) ; cnt . put ( s [ N ] , 1 ) ; while ( N > 1 ) { N /= s [ N ] ; if ( N != 0 && s [ N ] != 0 ) if ( ! cnt . containsKey ( s [ N ] ) ) cnt . put ( s [ N ] , 1 ) ; else cnt . put ( s [ N ] , cnt . get ( s [ N ] ) + 1 ) ; } if ( cnt . containsKey ( 0 ) ) cnt . remove ( 0 ) ; int totfactor = 1 ; for ( Map . Entry < Integer , Integer > i : cnt . entrySet ( ) ) totfactor *= i . getValue ( ) + 1 ; return totfactor ; } static 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 ; } public static void main ( String [ ] args ) { int N = 10 ; sieveOfEratosthenes ( N ) ; System . out . print ( countTriplets ( N ) ) ; } }