Smith Number | Python program to to check whether a number is Smith Number or not . ; array to store all prime less than and equal to 10 ^ 6 ; utility function for sieve of sundaram ; In general Sieve of Sundaram , produces primes smaller than ( 2 * x + 2 ) for a number given number x . Since we want primes smaller than MAX , we reduce MAX to half This array is used to separate numbers of the form i + j + 2 ij from others where 1 <= i <= j ; Main logic of Sundaram . Mark all numbers which do not generate prime number by doing 2 * i + 1 ; Since 2 is a prime number ; Print other primes . Remaining primes are of the form 2 * i + 1 such that marked [ i ] is false . ; Returns true if n is a Smith number , else false . ; Find sum the digits of prime factors of n ; If primes [ i ] is a prime factor , add its digits to pDigitSum . ; If n != 1 then one prime factor still to be summed up ; All prime factors digits summed up Now sum the original number digits ; If sum of digits in prime factors and sum of digits in original number are same , then return true . Else return false . ; Driver method Finding all prime numbers before limit . These numbers are used to find prime factors .
import math NEW_LINE MAX = 10000 NEW_LINE primes = [ ] NEW_LINE def sieveSundaram ( ) : NEW_LINE INDENT marked = [ 0 ] * ( ( MAX / 2 ) + 100 ) NEW_LINE i = 1 NEW_LINE while i <= ( ( math . sqrt ( MAX ) - 1 ) / 2 ) : NEW_LINE INDENT j = ( i * ( i + 1 ) ) << 1 NEW_LINE while j <= MAX / 2 : NEW_LINE INDENT marked [ j ] = 1 NEW_LINE j = j + 2 * i + 1 NEW_LINE DEDENT i = i + 1 NEW_LINE DEDENT primes . append ( 2 ) NEW_LINE i = 1 NEW_LINE while i <= MAX / 2 : NEW_LINE INDENT if marked [ i ] == 0 : NEW_LINE INDENT primes . append ( 2 * i + 1 ) NEW_LINE DEDENT i = i + 1 NEW_LINE 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 = i + 1 NEW_LINE DEDENT if not n == 1 and not 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 sieveSundaram ( ) ; NEW_LINE print " Printing ▁ first ▁ few ▁ Smith ▁ Numbers ▁ using ▁ isSmith ( ) " NEW_LINE i = 1 NEW_LINE while i < 500 : NEW_LINE INDENT if isSmith ( i ) : NEW_LINE INDENT print i , NEW_LINE DEDENT i = i + 1 NEW_LINE DEDENT