números económicos

Posted on by Rudeus Greyrat

Número económico es un número N si el número de dígitos en la factorización prima de N (incluidas las potencias) es menor que el número de dígitos en N.
Los primeros números económicos son: 
 

125, 128, 243, 256, 343, 512, 625, 729, … 
 

Encuentre los números económicos menores que N

Dado un número N , la tarea es imprimir todos los Números Económicos hasta N .
Ejemplos: 
 

Entrada: N = 200 
Salida: 125 128
Entrada: N = 700 
Salida: 125 128 243 256 343 512 625 
 

Acercarse: 
 

  1. Cuente todos los números primos hasta 10^6 usando Sieve of Sundaram .
  2. Encuentra el número de dígitos en N.
  3. Encuentre todos los factores primos de N y haga lo siguiente para cada factor primo P. 
    • Encuentra el número de dígitos en P.
    • Cuente la potencia más alta de P que divide a N.
    • Encuentre la suma de los dos anteriores.
  4. Si los dígitos en factores primos son menores que los dígitos en el número original, devuelve verdadero. De lo contrario, devuelve falso.

A continuación se muestra la implementación del enfoque:
 

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
Producción: 

125 128

 

Complejidad de tiempo: O (n 1/2 )

Espacio Auxiliar: O(1)

Referencia : https://mathworld.wolfram.com/EconomicalNumber.html
 

Publicación traducida automáticamente

Artículo escrito por spp____ y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *