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
< ? php function primes ( $ n ) { $ prime = array ( ) ; for ( $ i = 0 ; $ i < $ n + 1 ; $ i ++ ) $ prime [ $ i ] = true ; for ( $ i = 2 ; $ i * $ i <= $ n ; $ i ++ ) { if ( $ prime [ $ i ] == true ) { for ( $ j = $ i * 2 ; $ j <= $ n ; $ j += $ i ) $ prime [ $ j ] = false ; } } $ arr = array ( ) ; for ( $ i = 2 ; $ i < $ n ; $ i ++ ) if ( $ prime [ $ i ] ) array_push ( $ arr , $ i ) ; return $ arr ; } function countDigits ( $ n ) { $ temp = $ n ; $ c = 0 ; while ( $ temp != 0 ) { $ temp = intval ( $ temp / 10 ) ; $ c ++ ; } return $ c ; } function frugal ( $ n ) { $ r = primes ( $ n ) ; $ t = $ n ; $ s = 0 ; for ( $ i = 0 ; $ i < count ( $ r ) ; $ i ++ ) { if ( $ t % $ r [ $ i ] == 0 ) { $ k = 0 ; while ( $ t % $ r [ $ i ] == 0 ) { $ t = intval ( $ t / $ r [ $ i ] ) ; $ k ++ ; } if ( $ k == 1 ) $ s = $ s + countDigits ( $ r [ $ i ] ) ; else if ( $ k != 1 ) $ s = $ s + countDigits ( $ r [ $ i ] ) + countDigits ( $ k ) ; } } return ( countDigits ( $ n ) > $ s && $ s != 0 ) ; } $ n = 343 ; if ( frugal ( $ n ) ) echo ( " A ▁ Frugal ▁ number STRNEWLINE " ) ; else echo ( " Not ▁ a ▁ frugal ▁ number STRNEWLINE " ) ; ? >