text: Wasteful Numbers | C # program for the above approach ; Array to store all prime less than and equal to MAX . ; Function for Sieve of Sundaram ; Boolean Array ; Mark all numbers which do not generate prime number by 2 * i + 1 ; Since 2 is a prime number ; Print remaining primes are of the form 2 * i + 1 such that marked [ i ] is false . ; Function that returns true if n is a Wasteful 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 more than digits in original number then return true . Else return false . ; Function to print Wasteful Number before N ; Iterate till N and check if i is wastefull or not ; Driver code ; Precompute prime numbers upto 10 ^ 6 ; Function Call
code: using System ; using System . Collections . Generic ; class GFG { static int MAX = 10000 ; static List < int > primes = new List < int > ( ) ; static void sieveSundaram ( ) { bool [ ] marked = new bool [ MAX / 2 + 1 ] ; for ( int i = 1 ; i <= ( Math . Sqrt ( MAX ) - 1 ) / 2 ; i ++ ) { for ( int j = ( i * ( i + 1 ) ) << 1 ; j <= MAX / 2 ; j = j + 2 * i + 1 ) { marked [ j ] = true ; } } primes . Add ( 2 ) ; for ( int i = 1 ; i <= MAX / 2 ; i ++ ) if ( marked [ i ] == false ) primes . Add ( 2 * i + 1 ) ; } static bool isWasteful ( int n ) { if ( n == 1 ) return false ; int original_no = n ; int sumDigits = 0 ; while ( original_no > 0 ) { sumDigits ++ ; original_no = original_no / 10 ; } int pDigit = 0 , count_exp = 0 , p = 0 ; for ( int i = 0 ; primes [ i ] <= n / 2 ; i ++ ) { while ( n % primes [ i ] == 0 ) { p = primes [ i ] ; n = n / p ; count_exp ++ ; } while ( p > 0 ) { pDigit ++ ; p = p / 10 ; } while ( count_exp > 1 ) { pDigit ++ ; count_exp = count_exp / 10 ; } } if ( n != 1 ) { while ( n > 0 ) { pDigit ++ ; n = n / 10 ; } } return ( pDigit > sumDigits ) ; } static void Solve ( int N ) { for ( int i = 1 ; i < N ; i ++ ) { if ( isWasteful ( i ) ) { Console . Write ( i + " ▁ " ) ; } } } public static void Main ( String [ ] args ) { sieveSundaram ( ) ; int N = 10 ; Solve ( N ) ; } }