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 ; Iterate through all pairs ; Increment count if there is a smith brother pair ; Driver code ; Preprocessing ; Input ; Function call
using System ; using System . Collections . Generic ; class GFG { static int MAX = 10000 ; static List < int > primes = new List < int > ( ) ; static void sieveSundaram ( ) { int [ ] marked = new int [ MAX / 2 + 100 ] ; Array . Clear ( marked , 0 , MAX / 2 + 100 ) ; for ( int i = 1 ; i <= ( int ) ( Math . Sqrt ( MAX ) - 1 ) / 2 ; i ++ ) for ( int j = ( i * ( i + 1 ) ) << 1 ; j <= MAX / 2 ; j = j + 2 * i + 1 ) marked [ j ] = 1 ; primes . Add ( 2 ) ; for ( int i = 1 ; i <= ( int ) MAX / 2 ; i ++ ) if ( marked [ i ] == 0 ) primes . Add ( 2 * i + 1 ) ; } static 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 ) ; } static bool isSmithBrotherPair ( int X , int Y ) { return isSmith ( X ) && isSmith ( Y ) && Math . Abs ( X - Y ) == 1 ; } static int countSmithBrotherPairs ( int [ ] A , int N ) { int count = 0 ; for ( int i = 0 ; i < N ; i ++ ) for ( int j = i + 1 ; j < N ; j ++ ) { if ( isSmithBrotherPair ( A [ i ] , A [ j ] ) ) count ++ ; } return count ; } public static void Main ( ) { sieveSundaram ( ) ; int [ ] A = { 728 , 729 , 28 , 2964 , 2965 } ; int N = A . Length ; Console . Write ( countSmithBrotherPairs ( A , N ) ) ; } }