A frugal number is a number whose number of digits is strictly greater than the number of digits in its prime factorization (including exponents). If the exponent is 1 for a certain prime, involved in the prime factorization, then that exponent does not contribute to the number of digits in the prime factorization.
Some examples of frugal numbers are:
1) 125 =
, here the number of digits in the number is three (1, 2 and 5) which is strictly greater than the number of digits in its prime factorization which is two (5 and 3).
2) 512 =
3) 1029 = 3 ×
, here the number of digits in the number is three (1, 2 and 5) which is strictly greater than the number of digits in its prime factorization which is two (5 and 3). 
, here the number of digits in the number is three (5, 1 and 2) which is strictly greater than the number of digits in its prime factorization which is two (2 and 9).
, here the number of digits in the number is four (1, 0, 2 and 9) which is strictly greater than the number of digits its prime factorization which is three (3, 7 and 3).The first few frugal numbers are : 125, 128, 243, 256, 343, 512, 625, 729, ….
It may be noted here that prime numbers are not frugal numbers, since the number of digits in the prime factorization of a prime number is equal to the number of digits in the prime number (since exponents of value 1 are not considered).
Example 19 = 
, but the 1 in the exponent does not contribute to the number of digits in the prime factorization of the number. Hence the number of digits in the number is two (1 and 9), which is equal to the number of digits in its prime factorization (1 and 9).
A program to find whether a number, ‘n’ is frugal or not involves simple steps. First, we find all prime numbers upto ‘n’ and then find the prime factorization of n. Finally, we check whether the number of digits in n, is greater than the number of digits in the prime factorization of n.
C++
// Program to check for Frugal number#include <bits/stdc++.h>using namespace std;// Finding primes upto entered numbervector<long long int> primes(long long int n){ bool prime[n + 1]; // Finding primes by Sieve of Eratosthenes method memset(prime, true, sizeof(prime)); for (int i = 2; i * i <= n; i++) { // If prime[i] is not changed, then it is prime if (prime[i] == true) { // Update all multiples of p for (int j = i * 2; j <= n; j += i) prime[j] = false; } } // Forming array of the prime numbers found vector<long long int> arr; for (int i = 2; i < n; i++) if (prime[i]) arr.push_back(i); return arr;}// Returns number of digits in nint countDigits(long long int n){ long long int temp = n; int c = 0; while (temp != 0) { temp = temp / 10; c++; } return c;}// Checking whether a number is Frugal or notbool frugal(long long int n){ vector<long long int> r = primes(n); long long int t = n; // Finding number of digits in prime // factorization of the number long long int s = 0; for (int i = 0; i < r.size(); i++) { if (t % r[i] == 0) { // Exponent for current factor long long int k = 0; // Counting number of times this prime // factor divides (Finding exponent) while (t % r[i] == 0) { t = t / r[i]; k++; } // Finding number of digits in the exponent // Avoiding exponents of value 1 if (k == 1) s = s + countDigits(r[i]); else if (k != 1) s = s + countDigits(r[i]) + countDigits(k); } } // Checking condition for frugal number return (countDigits(n) > s && s != 0);}// Driver Method to check for frugal numberint main(){ long long int n = 343; if (frugal(n)) cout << "A Frugal number\n"; else cout << "Not a frugal number\n"; return 0;} |
Java
// Program to check // for Frugal numberimport java.io.*;import java.util.*;class GFG{ // Finding primes upto // entered number static ArrayList<Long> primes(long n) { boolean []prime = new boolean[(int)n + 1]; for(int i = 0; i < n + 1; i++) prime[i] = true; // Finding primes by Sieve // of Eratosthenes method for (int i = 2; i * i <= n; i++) { // If prime[i] is not // changed, then it // is prime if (prime[i] == true) { // Update all // multiples of p for (int j = i * 2; j <= n; j += i) prime[j] = false; } } // Forming array of the // prime numbers found ArrayList<Long> arr = new ArrayList<Long>(); for (int i = 2; i < n; i++) if (prime[i]) arr.add((long)i); return arr; } // Returns number // of digits in n static int countDigits(long n) { long temp = n; int c = 0; while (temp != 0) { temp = temp / 10; c++; } return c; } // Checking whether a // number is Frugal or not static boolean frugal(long n) { ArrayList<Long> r = primes(n); long t = n; // Finding number of digits // in prime factorization // of the number long s = 0; for (int i = 0; i < r.size(); i++) { if (t % r.get(i) == 0) { // Exponent for // current factor long k = 0; // Counting number of times // this prime factor divides // (Finding exponent) while (t % r.get(i) == 0) { t = t / r.get(i); k++; } // Finding number of digits // in the exponent Avoiding // exponents of value 1 if (k == 1) s = s + countDigits(r.get(i)); else if (k != 1) s = s + countDigits(r.get(i)) + countDigits(k); } } // Checking condition // for frugal number return (countDigits(n) > s && s != 0); } // Driver Code public static void main(String[] args) { long n = 343; if (frugal(n)) System.out.print("A Frugal number\n"); else System.out.print("Not a frugal number\n"); }}// This code is contributed by // Manish Shaw(manishshaw1) |
Python3
# Program to check for Frugal number# Finding primes upto entered numberdef primes(n): # Finding primes by Sieve # of Eratosthenes method prime = [True] * (n + 1); i = 2; while (i * i <= n): # If prime[i] is not changed, # then it is prime if (prime[i] == True): # Update all multiples of p j = i * 2; while (j <= n): prime[j] = False; j += i; i += 1; # Forming array of the prime # numbers found arr = []; for i in range(2, n): if (prime[i]): arr.append(i); return arr;# Returns number of digits in ndef countDigits(n): temp = n; c = 0; while (temp != 0): temp = int(temp / 10); c += 1; return c;# Checking whether a number is# Frugal or notdef frugal(n): r = primes(n); t = n; # Finding number of digits # in prime factorization # of the number s = 0; for i in range(len(r)): if (t % r[i] == 0): # Exponent for current factor k = 0; # Counting number of times # this prime factor divides # (Finding exponent) while (t % r[i] == 0): t = int(t / r[i]); k += 1; # Finding number of digits # in the exponent Avoiding # exponents of value 1 if (k == 1): s = s + countDigits(r[i]); elif (k != 1): s = (s + countDigits(r[i]) + countDigits(k)); # Checking condition # for frugal number return (countDigits(n) > s and s != 0);# Driver Coden = 343;if (frugal(n)): print("A Frugal number");else: print("Not a frugal number"); # This code is contributed by # mits |
C#
// Program to check for Frugal numberusing System;using System.Collections.Generic;class GFG{ // Finding primes upto // entered number static List<long> primes(long n) { bool []prime = new bool[n + 1]; for(int i = 0; i < n + 1; i++) prime[i] = true; // Finding primes by Sieve // of Eratosthenes method for (int i = 2; i * i <= n; i++) { // If prime[i] is not // changed, then it is prime if (prime[i] == true) { // Update all multiples of p for (int j = i * 2; j <= n; j += i) prime[j] = false; } } // Forming array of the // prime numbers found List<long> arr = new List<long>(); for (int i = 2; i < n; i++) if (prime[i]) arr.Add(i); return arr; } // Returns number of digits in n static int countDigits(long n) { long temp = n; int c = 0; while (temp != 0) { temp = temp / 10; c++; } return c; } // Checking whether a number // is Frugal or not static bool frugal(long n) { List<long> r = primes(n); long t = n; // Finding number of digits in prime // factorization of the number long s = 0; for (int i = 0; i < r.Count; i++) { if (t % r[i] == 0) { // Exponent for current factor long k = 0; // Counting number of times // this prime factor divides // (Finding exponent) while (t % r[i] == 0) { t = t / r[i]; k++; } // Finding number of digits // in the exponent Avoiding // exponents of value 1 if (k == 1) s = s + countDigits(r[i]); else if (k != 1) s = s + countDigits(r[i]) + countDigits(k); } } // Checking condition // for frugal number return (countDigits(n) > s && s != 0); } // Driver Code static void Main() { long n = 343; if (frugal(n)) Console.Write("A Frugal number\n"); else Console.Write("Not a frugal number\n"); }}// This code is contributed by // Manish Shaw(manishshaw1) |
PHP
<?php// Program to check for Frugal number// Finding primes upto // entered numberfunction primes($n){ $prime = array(); // Finding primes by Sieve // of Eratosthenes method for($i = 0; $i < $n + 1; $i++) $prime[$i] = true; for ($i = 2; $i * $i <= $n; $i++) { // If prime[i] is not changed, // then it is prime if ($prime[$i] == true) { // Update all multiples of p for ($j = $i * 2; $j <= $n; $j += $i) $prime[$j] = false; } } // Forming array of the // prime numbers found $arr = array(); for ($i = 2; $i < $n; $i++) if ($prime[$i]) array_push($arr, $i); return $arr;}// Returns number // of digits in nfunction countDigits($n){ $temp = $n; $c = 0; while ($temp != 0) { $temp = intval($temp / 10); $c++; } return $c;}// Checking whether a // number is Frugal or notfunction frugal($n){ $r = primes($n); $t = $n; // Finding number of digits // in prime factorization // of the number $s = 0; for ($i = 0; $i < count($r); $i++) { if ($t % $r[$i] == 0) { // Exponent for // current factor $k = 0; // Counting number of times // this prime factor divides // (Finding exponent) while ($t % $r[$i] == 0) { $t = intval($t / $r[$i]); $k++; } // Finding number of digits // in the exponent Avoiding // exponents of value 1 if ($k == 1) $s = $s + countDigits($r[$i]); else if ($k != 1) $s = $s + countDigits($r[$i]) + countDigits($k); } } // Checking condition // for frugal number return (countDigits($n) > $s && $s != 0);} // Driver Code$n = 343;if (frugal($n)) echo ("A Frugal number\n");else echo ("Not a frugal number\n"); // This code is contributed by // Manish Shaw(manishshaw1)?> |
Javascript
<script>// Program to check for Frugal number// Finding primes upto entered numberfunction primes(n){ var prime = Array(n+1).fill(true); // Finding primes by Sieve of Eratosthenes method for (var i = 2; i * i <= n; i++) { // If prime[i] is not changed, then it is prime if (prime[i] == true) { // Update all multiples of p for (var j = i * 2; j <= n; j += i) prime[j] = false; } } // Forming array of the prime numbers found var arr = []; for (var i = 2; i < n; i++) if (prime[i]) arr.push(i); return arr;}// Returns number of digits in nfunction countDigits(n){ var temp = n; var c = 0; while (temp != 0) { temp = parseInt(temp / 10); c++; } return c;}// Checking whether a number is Frugal or notfunction frugal(n){ var r = primes(n); var t = n; // Finding number of digits in prime // factorization of the number var s = 0; for (var i = 0; i < r.length; i++) { if (t % r[i] == 0) { // Exponent for current factor var k = 0; // Counting number of times this prime // factor divides (Finding exponent) while (t % r[i] == 0) { t = parseInt(t / r[i]); k++; } // Finding number of digits in the exponent // Avoiding exponents of value 1 if (k == 1) s = s + countDigits(r[i]); else if (k != 1) s = s + countDigits(r[i]) + countDigits(k); } } // Checking condition for frugal number return (countDigits(n) > s && s != 0);}// Driver Method to check for frugal numbervar n = 343;if (frugal(n)) document.write( "A Frugal number");else document.write( "Not a frugal number");// This code is contributed by rrrtnx.</script> |
Output:
A Frugal number
Time Complexity: O(nlog(logn))
Auxiliary Space: O(n)
Please suggest if someone has a better solution which is more efficient in terms of space and time.
Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above
Optimization :
The above code can be optimized using the approach discussed in Print all prime factors and their powers
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
