Equidigital Numbers | Python3 Program to find Equidigital Numbers till n ; Array to store all prime less than and equal to MAX . ; 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 Equidigital number , else false . ; Count digits in original number ; Count all digits in prime factors of n pDigit is going to hold this value . ; Count powers of p in n ; If primes [ i ] is a prime factor , ; Count the power of prime factors ; Add its digits to pDigit . ; Add digits of power of prime factors to pDigit . ; If n != 1 then one prime factor still to be summed up ; ; If digits in prime factors and 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 .
import math NEW_LINE MAX = 10000 ; NEW_LINE primes = [ ] ; NEW_LINE def sieveSundaram ( ) : NEW_LINE INDENT marked = [ False ] * int ( MAX / 2 + 1 ) ; NEW_LINE for i in range ( 1 , int ( ( math . sqrt ( MAX ) - 1 ) / 2 ) + 1 ) : NEW_LINE INDENT for j in range ( ( i * ( i + 1 ) ) << 1 , int ( MAX / 2 ) + 1 , 2 * i + 1 ) : NEW_LINE INDENT marked [ j ] = True ; NEW_LINE DEDENT DEDENT primes . append ( 2 ) ; NEW_LINE for i in range ( 1 , int ( MAX / 2 ) + 1 ) : NEW_LINE INDENT if ( marked [ i ] == False ) : NEW_LINE INDENT primes . append ( 2 * i + 1 ) ; NEW_LINE DEDENT DEDENT DEDENT def isEquidigital ( n ) : NEW_LINE INDENT if ( n == 1 ) : NEW_LINE INDENT return True ; NEW_LINE DEDENT original_no = n ; NEW_LINE sumDigits = 0 ; NEW_LINE while ( original_no > 0 ) : NEW_LINE INDENT sumDigits += 1 ; NEW_LINE original_no = int ( original_no / 10 ) ; NEW_LINE DEDENT pDigit = 0 ; NEW_LINE count_exp = 0 ; NEW_LINE p = 0 ; NEW_LINE i = 0 ; NEW_LINE while ( primes [ i ] <= int ( n / 2 ) ) : NEW_LINE INDENT while ( n % primes [ i ] == 0 ) : NEW_LINE INDENT p = primes [ i ] ; NEW_LINE n = int ( n / p ) ; NEW_LINE count_exp += 1 ; NEW_LINE DEDENT while ( p > 0 ) : NEW_LINE INDENT pDigit += 1 ; NEW_LINE p = int ( p / 10 ) ; NEW_LINE DEDENT while ( count_exp > 1 ) : NEW_LINE INDENT pDigit += 1 ; NEW_LINE count_exp = int ( count_exp / 10 ) ; NEW_LINE DEDENT i += 1 ; NEW_LINE DEDENT if ( n != 1 ) : NEW_LINE INDENT while ( n > 0 ) : NEW_LINE INDENT pDigit += 1 ; NEW_LINE n = int ( n / 10 ) ; NEW_LINE DEDENT DEDENT return ( pDigit == sumDigits ) ; NEW_LINE DEDENT sieveSundaram ( ) ; NEW_LINE print ( " Printing ▁ first ▁ few ▁ Equidigital " , " Numbers ▁ using ▁ isEquidigital ( ) " ) ; NEW_LINE for i in range ( 1 , 20 ) : NEW_LINE INDENT if ( isEquidigital ( i ) ) : NEW_LINE INDENT print ( i , end = " ▁ " ) ; NEW_LINE DEDENT DEDENT