Economical Numbers | Python3 implementation to find Economical 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 ; Main logic of Sundaram . Mark all numbers which do not generate prime number by doing 2 * i + 1 ; Since 2 is a prime number ; Prother primes . Remaining primes are of the form 2 * i + 1 such that marked [ i ] is false . ; Function to check if a number is a Economical number ; 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 is less than digits in original number 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 = [ 0 ] * ( MAX // 2 + 1 ) NEW_LINE for i in range ( 1 , ( int ( math . sqrt ( MAX ) ) - 1 ) // 2 + 1 ) : NEW_LINE INDENT j = ( i * ( i + 1 ) ) << 1 NEW_LINE while ( j <= MAX // 2 ) : NEW_LINE INDENT marked [ j ] = True NEW_LINE j = j + 2 * i + 1 NEW_LINE DEDENT DEDENT primes . append ( 2 ) NEW_LINE for i in range ( 1 , MAX // 2 + 1 ) : NEW_LINE INDENT if ( marked [ i ] == False ) : NEW_LINE INDENT primes . append ( 2 * i + 1 ) NEW_LINE DEDENT DEDENT DEDENT def isEconomical ( n ) : NEW_LINE INDENT if ( n == 1 ) : NEW_LINE INDENT return False 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 = original_no // 10 NEW_LINE DEDENT pDigit = 0 NEW_LINE count_exp = 0 NEW_LINE i = 0 NEW_LINE p = 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 count_exp += 1 NEW_LINE DEDENT i += 1 NEW_LINE while ( p > 0 ) : NEW_LINE INDENT pDigit += 1 NEW_LINE p = p // 10 NEW_LINE DEDENT while ( count_exp > 1 ) : NEW_LINE INDENT pDigit += 1 NEW_LINE count_exp = count_exp // 10 NEW_LINE DEDENT DEDENT if ( n != 1 ) : NEW_LINE INDENT while ( n > 0 ) : NEW_LINE INDENT pDigit += 1 NEW_LINE n = n // 10 NEW_LINE DEDENT DEDENT if ( pDigit < sumDigits ) : NEW_LINE INDENT return True NEW_LINE DEDENT return False NEW_LINE DEDENT sieveSundaram ( ) NEW_LINE for i in range ( 1 , 200 ) : NEW_LINE INDENT if ( isEconomical ( i ) ) : NEW_LINE INDENT print ( i , end = " ▁ " ) NEW_LINE DEDENT DEDENT