Find the count of Smith Brothers Pairs in a given Array | C ++ program for the above approach ; array to store all prime less than and equal to MAX ; utility function for sieve of sundaram ; Main logic of Sundaram . ; Since 2 is a prime number ; only primes are selected ; Function to check whether a number is a smith number . ; Find sum the digits of prime factors of n ; add its digits of prime factors to pDigitSum . ; one prime factor is still to be summed up ; Now sum the digits of the original number ; return the answer ; Function to check if X and Y are a Smith Brother Pair ; Function to find pairs from array ; Variable to store number of Smith Brothers Pairs ; sort A ; check for consecutive numbers only ; Driver code ; Preprocessing sieve of sundaram ; Input ; Function call
#include <bits/stdc++.h> NEW_LINE using namespace std ; const int MAX = 10000 ; vector < int > primes ; void sieveSundaram ( ) { bool marked [ MAX / 2 + 100 ] = { 0 } ; for ( int i = 1 ; i <= ( sqrt ( MAX ) - 1 ) / 2 ; i ++ ) for ( int j = ( i * ( i + 1 ) ) << 1 ; j <= MAX / 2 ; j = j + 2 * i + 1 ) marked [ j ] = true ; primes . push_back ( 2 ) ; for ( int i = 1 ; i <= MAX / 2 ; i ++ ) if ( marked [ i ] == false ) primes . push_back ( 2 * i + 1 ) ; } bool isSmith ( int n ) { int original_no = n ; int pDigitSum = 0 ; for ( int i = 0 ; primes [ i ] <= n / 2 ; i ++ ) { while ( n % primes [ i ] == 0 ) { int p = primes [ i ] ; n = n / p ; while ( p > 0 ) { pDigitSum += ( p % 10 ) ; p = p / 10 ; } } } if ( n != 1 && n != original_no ) { while ( n > 0 ) { pDigitSum = pDigitSum + n % 10 ; n = n / 10 ; } } int sumDigits = 0 ; while ( original_no > 0 ) { sumDigits = sumDigits + original_no % 10 ; original_no = original_no / 10 ; } return ( pDigitSum == sumDigits ) ; } bool isSmithBrotherPair ( int X , int Y ) { return isSmith ( X ) && isSmith ( Y ) ; } int countSmithBrotherPairs ( int A [ ] , int N ) { int count = 0 ; sort ( A , A + N ) ; for ( int i = 0 ; i < N - 2 ; i ++ ) if ( isSmithBrotherPair ( A [ i ] , A [ i + 1 ] ) ) count ++ ; return count ; } int main ( ) { sieveSundaram ( ) ; int A [ ] = { 728 , 729 , 28 , 2964 , 2965 } ; int N = sizeof ( A ) / sizeof ( A [ 0 ] ) ; cout << countSmithBrotherPairs ( A , N ) << endl ; return 0 ; }