Frugal Number | Program to check for 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
import java . io . * ; import java . util . * ; class GFG { static ArrayList < Long > primes ( long n ) { boolean [ ] prime = new boolean [ ( int ) n + 1 ] ; for ( int i = 0 ; i < n + 1 ; i ++ ) prime [ i ] = true ; for ( int i = 2 ; i * i <= n ; i ++ ) { if ( prime [ i ] == true ) { for ( int j = i * 2 ; j <= n ; j += i ) prime [ j ] = false ; } } ArrayList < Long > arr = new ArrayList < Long > ( ) ; for ( int i = 2 ; i < n ; i ++ ) if ( prime [ i ] ) arr . add ( ( long ) i ) ; return arr ; } static int countDigits ( long n ) { long temp = n ; int c = 0 ; while ( temp != 0 ) { temp = temp / 10 ; c ++ ; } return c ; } static boolean frugal ( long n ) { ArrayList < Long > r = primes ( n ) ; long t = n ; long s = 0 ; for ( int i = 0 ; i < r . size ( ) ; i ++ ) { if ( t % r . get ( i ) == 0 ) { long k = 0 ; while ( t % r . get ( i ) == 0 ) { t = t / r . get ( i ) ; k ++ ; } if ( k == 1 ) s = s + countDigits ( r . get ( i ) ) ; else if ( k != 1 ) s = s + countDigits ( r . get ( i ) ) + countDigits ( k ) ; } } return ( countDigits ( n ) > s && s != 0 ) ; } public static void main ( String [ ] args ) { long n = 343 ; if ( frugal ( n ) ) System . out . print ( "A Frugal numberNEW_LINE"); else System . out . print ( "Not a frugal numberNEW_LINE"); } }