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 Method to check for frugal number
#include <bits/stdc++.h> NEW_LINE using namespace std ; vector < long long int > primes ( long long int n ) { bool prime [ n + 1 ] ; memset ( prime , true , sizeof ( prime ) ) ; for ( int i = 2 ; i * i <= n ; i ++ ) { if ( prime [ i ] == true ) { for ( int j = i * 2 ; j <= n ; j += i ) prime [ j ] = false ; } } vector < long long int > arr ; for ( int i = 2 ; i < n ; i ++ ) if ( prime [ i ] ) arr . push_back ( i ) ; return arr ; } int countDigits ( long long int n ) { long long int temp = n ; int c = 0 ; while ( temp != 0 ) { temp = temp / 10 ; c ++ ; } return c ; } bool frugal ( long long int n ) { vector < long long int > r = primes ( n ) ; long long int t = n ; long long int s = 0 ; for ( int i = 0 ; i < r . size ( ) ; i ++ ) { if ( t % r [ i ] == 0 ) { long long int k = 0 ; while ( t % r [ i ] == 0 ) { t = 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 ) ; } int main ( ) { long long int n = 343 ; if ( frugal ( n ) ) cout << " A ▁ Frugal ▁ number STRNEWLINE " ; else cout << " Not ▁ a ▁ frugal ▁ number STRNEWLINE " ; return 0 ; }