Find the count of Smith Brothers Pairs in a given Array | Python3 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
from math import sqrt NEW_LINE MAX = 10000 NEW_LINE primes = [ ] NEW_LINE def sieveSundaram ( ) : NEW_LINE INDENT marked = [ 0 for i in range ( MAX // 2 + 100 ) ] NEW_LINE j = 0 NEW_LINE for i in range ( 1 , int ( ( sqrt ( MAX ) - 1 ) / 2 ) + 1 , 1 ) : NEW_LINE INDENT for j in range ( ( i * ( i + 1 ) ) << 1 , MAX // 2 + 1 , j + 2 * i + 1 ) : NEW_LINE INDENT marked [ j ] = True NEW_LINE DEDENT DEDENT primes . append ( 2 ) NEW_LINE for i in range ( 1 , MAX // 2 + 1 , 1 ) : NEW_LINE INDENT if ( marked [ i ] == False ) : NEW_LINE INDENT primes . append ( 2 * i + 1 ) NEW_LINE DEDENT DEDENT DEDENT def isSmith ( n ) : NEW_LINE INDENT original_no = n NEW_LINE pDigitSum = 0 NEW_LINE i = 0 NEW_LINE while ( primes [ i ] <= n // 2 ) : NEW_LINE INDENT while ( n % primes [ i ] == 0 ) : NEW_LINE INDENT p = primes [ i ] NEW_LINE n = n // p NEW_LINE while ( p > 0 ) : NEW_LINE INDENT pDigitSum += ( p % 10 ) NEW_LINE p = p // 10 NEW_LINE DEDENT DEDENT i += 1 NEW_LINE DEDENT if ( n != 1 and n != original_no ) : NEW_LINE INDENT while ( n > 0 ) : NEW_LINE INDENT pDigitSum = pDigitSum + n % 10 NEW_LINE n = n // 10 NEW_LINE DEDENT DEDENT sumDigits = 0 NEW_LINE while ( original_no > 0 ) : NEW_LINE INDENT sumDigits = sumDigits + original_no % 10 NEW_LINE original_no = original_no // 10 NEW_LINE DEDENT return ( pDigitSum == sumDigits ) NEW_LINE DEDENT def isSmithBrotherPair ( X , Y ) : NEW_LINE INDENT return ( isSmith ( X ) and isSmith ( Y ) and abs ( X - Y ) == 1 ) NEW_LINE DEDENT def countSmithBrotherPairs ( A , N ) : NEW_LINE INDENT count = 0 NEW_LINE for i in range ( N ) : NEW_LINE INDENT for j in range ( i + 1 , N , 1 ) : NEW_LINE INDENT if ( isSmithBrotherPair ( A [ i ] , A [ j ] ) ) : NEW_LINE INDENT count += 1 NEW_LINE DEDENT DEDENT DEDENT return count NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT sieveSundaram ( ) NEW_LINE A = [ 728 , 729 , 28 , 2964 , 2965 ] NEW_LINE N = len ( A ) NEW_LINE print ( countSmithBrotherPairs ( A , N ) ) NEW_LINE DEDENT