Frugal Number | Finding primes upto entered number ; Finding primes by Sieve of Eratosthenes method ; If prime [ i ] is not changed , then it is prime ; Update all multiples of p ; Forming array of the prime numbers found ; Returns number of digits in n ; Checking whether a number is Frugal or not ; Finding number of digits in prime factorization of the number ; Exponent for current factor ; Counting number of times this prime factor divides ( Finding exponent ) ; Finding number of digits in the exponent Avoiding exponents of value 1 ; Checking condition for frugal number ; Driver Code
def primes ( n ) : NEW_LINE INDENT prime = [ True ] * ( n + 1 ) ; NEW_LINE i = 2 ; NEW_LINE while ( i * i <= n ) : NEW_LINE INDENT if ( prime [ i ] == True ) : NEW_LINE INDENT j = i * 2 ; NEW_LINE while ( j <= n ) : NEW_LINE INDENT prime [ j ] = False ; NEW_LINE j += i ; NEW_LINE DEDENT DEDENT i += 1 ; NEW_LINE DEDENT arr = [ ] ; NEW_LINE for i in range ( 2 , n ) : NEW_LINE INDENT if ( prime [ i ] ) : NEW_LINE INDENT arr . append ( i ) ; NEW_LINE DEDENT DEDENT return arr ; NEW_LINE DEDENT def countDigits ( n ) : NEW_LINE INDENT temp = n ; NEW_LINE c = 0 ; NEW_LINE while ( temp != 0 ) : NEW_LINE INDENT temp = int ( temp / 10 ) ; NEW_LINE c += 1 ; NEW_LINE DEDENT return c ; NEW_LINE DEDENT def frugal ( n ) : NEW_LINE INDENT r = primes ( n ) ; NEW_LINE t = n ; NEW_LINE s = 0 ; NEW_LINE for i in range ( len ( r ) ) : NEW_LINE INDENT if ( t % r [ i ] == 0 ) : NEW_LINE INDENT k = 0 ; NEW_LINE while ( t % r [ i ] == 0 ) : NEW_LINE INDENT t = int ( t / r [ i ] ) ; NEW_LINE k += 1 ; NEW_LINE DEDENT if ( k == 1 ) : NEW_LINE INDENT s = s + countDigits ( r [ i ] ) ; NEW_LINE DEDENT elif ( k != 1 ) : NEW_LINE INDENT s = ( s + countDigits ( r [ i ] ) + countDigits ( k ) ) ; NEW_LINE DEDENT DEDENT DEDENT return ( countDigits ( n ) > s and s != 0 ) ; NEW_LINE DEDENT n = 343 ; NEW_LINE if ( frugal ( n ) ) : NEW_LINE INDENT print ( " A ▁ Frugal ▁ number " ) ; NEW_LINE DEDENT else : NEW_LINE INDENT print ( " Not ▁ a ▁ frugal ▁ number " ) ; NEW_LINE DEDENT