Economical Number is a number N if the number of digits in the prime factorization of N (including powers) is less than the number of digits in N.
The first few Economical numbers are:
125, 128, 243, 256, 343, 512, 625, 729, …
Find the Economical numbers less than N
Given a number N, the task is to print all Economical Numbers upto N.
Examples:
Input: N = 200
Output: 125 128
Input: N = 700
Output: 125 128 243 256 343 512 625
Approach:
- Count all primes upto 10^6 using Sieve of Sundaram.
- Find number of digits in N.
- Find all prime factors of N and do following for every prime factor P.
- Find number of digits in P.
- Count highest power of P that divides N.
- Find sum of above two.
- If digits in prime factors is less than digits in original number then return true. Else return false.
Below is the implementation of the approach:
C++
// C++ implementation to find // Economical Numbers till n #include <bits/stdc++.h> using namespace std; const int MAX = 10000; // Array to store all prime less // than and equal to MAX. vector<int> primes; // Utility function for sieve of sundaram void sieveSundaram() { // In general Sieve of Sundaram, // produces primes smaller // than (2*x + 2) for a number // given number x. Since // we want primes smaller than MAX, // we reduce MAX to half bool marked[MAX / 2 + 1] = { 0 }; // Main logic of Sundaram. Mark all numbers which // do not generate prime number by doing 2*i+1 for (int i = 1; i <= (sqrt(MAX) - 1) / 2; i++) for (int j = (i * (i + 1)) << 1; j <= MAX / 2; j = j + 2 * i + 1) marked[j] = true; // Since 2 is a prime number primes.push_back(2); // Print other primes. Remaining primes are of the // form 2*i + 1 such that marked[i] is false. for (int i = 1; i <= MAX / 2; i++) if (marked[i] == false) primes.push_back(2 * i + 1); } // Function to check if a number is // a Economical number bool isEconomical(int n) { if (n == 1) return false; // Count digits in original number int original_no = n; int sumDigits = 0; while (original_no > 0) { sumDigits++; original_no = original_no / 10; } // Count all digits in prime factors of n // pDigit is going to hold this value. int pDigit = 0, count_exp = 0, p; for (int i = 0; primes[i] <= n / 2; i++) { // Count powers of p in n while (n % primes[i] == 0) { // If primes[i] is a prime factor, p = primes[i]; n = n / p; // Count the power of prime factors count_exp++; } // Add its digits to pDigit. while (p > 0) { pDigit++; p = p / 10; } // Add digits of power of // prime factors to pDigit. while (count_exp > 1) { pDigit++; count_exp = count_exp / 10; } } // If n!=1 then one prime // factor still to be // summed up; if (n != 1) { while (n > 0) { pDigit++; n = n / 10; } } // If digits in prime factors is less than // digits in original number then // return true. Else return false. return (pDigit < sumDigits); } // Driver code int main() { // Finding all prime numbers // before limit. These // numbers are used to // find prime factors. sieveSundaram(); for (int i = 1; i < 200; i++) if (isEconomical(i)) cout << i << " "; return 0; } |
Java
// Java implementation to find // Economical Numbers till n import java.util.*; class GFG{ static int MAX = 10000; // Array to store all prime less // than and equal to MAX. static Vector<Integer> primes = new Vector<Integer>(); // Utility function for sieve of sundaram static void sieveSundaram() { // In general Sieve of Sundaram, // produces primes smaller // than (2*x + 2) for a number // given number x. Since // we want primes smaller than MAX, // we reduce MAX to half boolean []marked = new boolean[MAX / 2 + 1]; // Main logic of Sundaram. Mark all numbers which // do not generate prime number by doing 2*i+1 for (int i = 1; i <= (Math.sqrt(MAX) - 1) / 2; i++) for (int j = (i * (i + 1)) << 1; j <= MAX / 2; j = j + 2 * i + 1) marked[j] = true; // Since 2 is a prime number primes.add(2); // Print other primes. Remaining primes are of the // form 2*i + 1 such that marked[i] is false. for (int i = 1; i <= MAX / 2; i++) if (marked[i] == false) primes.add(2 * i + 1); } // Function to check if a number is // a Economical number static boolean isEconomical(int n) { if (n == 1) return false; // Count digits in original number int original_no = n; int sumDigits = 0; while (original_no > 0) { sumDigits++; original_no = original_no / 10; } // Count all digits in prime factors of n // pDigit is going to hold this value. int pDigit = 0, count_exp = 0, p = 0; for (int i = 0; primes.get(i) <= n / 2; i++) { // Count powers of p in n while (n % primes.get(i) == 0) { // If primes[i] is a prime factor, p = primes.get(i); n = n / p; // Count the power of prime factors count_exp++; } // Add its digits to pDigit. while (p > 0) { pDigit++; p = p / 10; } // Add digits of power of // prime factors to pDigit. while (count_exp > 1) { pDigit++; count_exp = count_exp / 10; } } // If n!=1 then one prime // factor still to be // summed up; if (n != 1) { while (n > 0) { pDigit++; n = n / 10; } } // If digits in prime factors is less than // digits in original number then // return true. Else return false. return (pDigit < sumDigits); } // Driver code public static void main(String[] args) { // Finding all prime numbers // before limit. These // numbers are used to // find prime factors. sieveSundaram(); for (int i = 1; i < 200; i++) if (isEconomical(i)) System.out.print(i + " "); } } // This code is contributed by Rajput-Ji |
Python3
# Python3 implementation to find # Economical Numbers till n import math MAX = 10000 # Array to store all prime less # than and equal to MAX. primes = [] # Utility function for sieve of sundaram def sieveSundaram(): # In general Sieve of Sundaram, # produces primes smaller # than (2*x + 2) for a number # given number x. Since # we want primes smaller than MAX, # we reduce MAX to half marked = [0] * (MAX // 2 + 1) # Main logic of Sundaram. Mark all numbers which # do not generate prime number by doing 2*i+1 for i in range(1, (int(math.sqrt(MAX)) - 1) // 2 + 1): j = (i * (i + 1)) << 1 while(j <= MAX // 2): marked[j] = True j = j + 2 * i + 1 # Since 2 is a prime number primes.append(2) # Prother primes. Remaining primes are of the # form 2*i + 1 such that marked[i] is false. for i in range(1, MAX // 2 + 1): if (marked[i] == False): primes.append(2 * i + 1) # Function to check if a number is # a Economical number def isEconomical(n): if (n == 1): return False # Count digits in original number original_no = n sumDigits = 0 while (original_no > 0): sumDigits += 1 original_no = original_no // 10 # Count all digits in prime factors of n # pDigit is going to hold this value. pDigit = 0 count_exp = 0 i = 0 p = 0 while(primes[i] <= n // 2): # Count powers of p in n while (n % primes[i] == 0): # If primes[i] is a prime factor, p = primes[i] n = n // p # Count the power of prime factors count_exp += 1 i += 1 # Add its digits to pDigit. while (p > 0): pDigit += 1 p = p // 10 # Add digits of power of # prime factors to pDigit. while (count_exp > 1): pDigit += 1 count_exp = count_exp // 10 # If n!=1 then one prime # factor still to be # summed up if (n != 1): while (n > 0): pDigit += 1 n = n // 10 # If digits in prime factors is less than # digits in original number then # return true. Else return false. if (pDigit < sumDigits): return True return False # Driver code # Finding all prime numbers # before limit. These # numbers are used to # find prime factors. sieveSundaram() for i in range(1, 200): if (isEconomical(i)): print(i, end = " ") # This code is contributed by shubhamsingh10 |
C#
// C# implementation to find // Economical Numbers till n using System; using System.Collections.Generic; class GFG{ static int MAX = 10000; // Array to store all prime less // than and equal to MAX. static List<int> primes = new List<int>(); // Utility function for sieve of sundaram static void sieveSundaram() { // In general Sieve of Sundaram, // produces primes smaller // than (2*x + 2) for a number // given number x. Since // we want primes smaller than MAX, // we reduce MAX to half bool[] marked = new bool[MAX / 2 + 1]; // Main logic of Sundaram. Mark all numbers which // do not generate prime number by doing 2*i+1 for(int i = 1; i <= (Math.Sqrt(MAX) - 1) / 2; i++) for(int j = (i * (i + 1)) << 1; j <= MAX / 2; j = j + 2 * i + 1) marked[j] = true; // Since 2 is a prime number primes.Add(2); // Print other primes. Remaining primes are of the // form 2*i + 1 such that marked[i] is false. for(int i = 1; i <= MAX / 2; i++) if (marked[i] == false) primes.Add(2 * i + 1); } // Function to check if a number is // a Economical number static bool isEconomical(int n) { if (n == 1) return false; // Count digits in original number int original_no = n; int sumDigits = 0; while (original_no > 0) { sumDigits++; original_no = original_no / 10; } // Count all digits in prime factors of n // pDigit is going to hold this value. int pDigit = 0, count_exp = 0, p = 0; for(int i = 0; primes[i] <= n / 2; i++) { // Count powers of p in n while (n % primes[i] == 0) { // If primes[i] is a prime factor, p = primes[i]; n = n / p; // Count the power of prime factors count_exp++; } // Add its digits to pDigit. while (p > 0) { pDigit++; p = p / 10; } // Add digits of power of // prime factors to pDigit. while (count_exp > 1) { pDigit++; count_exp = count_exp / 10; } } // If n!=1 then one prime // factor still to be // summed up; if (n != 1) { while (n > 0) { pDigit++; n = n / 10; } } // If digits in prime factors is less than // digits in original number then // return true. Else return false. return (pDigit < sumDigits); } // Driver code public static void Main(String[] args) { // Finding all prime numbers // before limit. These // numbers are used to // find prime factors. sieveSundaram(); for(int i = 1; i < 200; i++) if (isEconomical(i)) Console.Write(i + " "); } } // This code is contributed by Rajput-Ji |
Javascript
// JS implementation to find // Economical Numbers till n let MAX = 10000; // Array to store all prime less // than and equal to MAX. let primes = []; // Utility function for sieve of sundaram function sieveSundaram() { // In general Sieve of Sundaram, // produces primes smaller // than (2*x + 2) for a number // given number x. Since // we want primes smaller than MAX, // we reduce MAX to half let marked = new Array(Math.floor(MAX / 2) + 1).fill(0) // Main logic of Sundaram. Mark all numbers which // do not generate prime number by doing 2*i+1 for (var i = 1; i <= (Math.sqrt(MAX) - 1) / 2; i++) for (var j = (i * (i + 1)) << 1; j <= MAX / 2; j = j + 2 * i + 1) marked[j] = true; // Since 2 is a prime number primes.push(2); // Print other primes. Remaining primes are of the // form 2*i + 1 such that marked[i] is false. for (var i = 1; i <= MAX / 2; i++) if (marked[i] == false) primes.push(2 * i + 1); } // Function to check if a number is // a Economical number function isEconomical(n) { if (n == 1) return false; // Count digits in original number let original_no = n; let sumDigits = 0; while (original_no > 0) { sumDigits++; original_no = Math.floor(original_no / 10); } // Count all digits in prime factors of n // pDigit is going to hold this value. let pDigit = 0, count_exp = 0, p; for (var i = 0; primes[i] <= n / 2; i++) { // Count powers of p in n while (n % primes[i] == 0) { // If primes[i] is a prime factor, p = primes[i]; n = n / p; // Count the power of prime factors count_exp++; } // Add its digits to pDigit. while (p > 0) { pDigit++; p = Math.floor(p / 10); } // Add digits of power of // prime factors to pDigit. while (count_exp > 1) { pDigit++; count_exp = Math.floor(count_exp / 10); } } // If n!=1 then one prime // factor still to be // summed up; if (n != 1) { while (n > 0) { pDigit++; n = Math.floor(n / 10); } } // If digits in prime factors is less than // digits in original number then // return true. Else return false. return (pDigit < sumDigits); } // Driver code // Finding all prime numbers // before limit. These // numbers are used to // find prime factors. sieveSundaram(); for (var i = 1; i < 200; i++) if (isEconomical(i)) process.stdout.write(i + " "); // This code is contributed by phasing17. |
Output:
125 128
Time Complexity: O(n1/2)
Auxiliary Space: O(1)
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!
