Smith Number | PHP 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 . ; Finding all prime numbers before limit . These numbers are used to find prime factors .
< ? php $ MAX = 10000 ; $ primes = array ( ) ; function sieveSundaram ( ) { global $ MAX , $ primes ; $ marked = array_fill ( 0 , ( $ MAX / 2 + 100 ) , false ) ; for ( $ i = 1 ; $ i <= ( sqrt ( $ MAX ) - 1 ) / 2 ; $ i ++ ) for ( $ j = ( $ i * ( $ i + 1 ) ) << 1 ; $ j <= $ MAX / 2 ; $ j = $ j + 2 * $ i + 1 ) $ marked [ $ j ] = true ; array_push ( $ primes , 2 ) ; for ( $ i = 1 ; $ i <= $ MAX / 2 ; $ i ++ ) if ( $ marked [ $ i ] == false ) array_push ( $ primes , 2 * $ i + 1 ) ; } function isSmith ( $ n ) { global $ MAX , $ primes ; $ original_no = $ n ; $ pDigitSum = 0 ; for ( $ i = 0 ; $ primes [ $ i ] <= $ n / 2 ; $ i ++ ) { while ( $ n % $ primes [ $ i ] == 0 ) { $ 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 ; } } $ sumDigits = 0 ; while ( $ original_no > 0 ) { $ sumDigits = $ sumDigits + $ original_no % 10 ; $ original_no = $ original_no / 10 ; } return ( $ pDigitSum == $ sumDigits ) ; } sieveSundaram ( ) ; echo " Printing ▁ first ▁ few ▁ Smith ▁ Numbers " . " ▁ using ▁ isSmith ( ) STRNEWLINE " ; for ( $ i = 1 ; $ i < 500 ; $ i ++ ) if ( isSmith ( $ i ) ) echo $ i . " " ; ? >