número frugal

Posted on by Rudeus Greyrat

Un número frugal es un número cuyo número de dígitos es estrictamente mayor que el número de dígitos en su descomposición en factores primos (incluidos los exponentes). Si el exponente es 1 para cierto primo, involucrado en la descomposición en factores primos, entonces ese exponente no contribuye al número de dígitos en la descomposición en factores primos.
Algunos ejemplos de números frugales son:
 

1) 125 =  5^3 , aquí el número de dígitos en el número es tres (1, 2 y 5) que es estrictamente mayor que el número de dígitos en su descomposición en factores primos que es dos (5 y 3). 
2) 512 =  2^9 , aquí el número de dígitos en el número es tres (5, 1 y 2) que es estrictamente mayor que el número de dígitos en su descomposición en factores primos que es dos (2 y 9).
3) 1029 = 3 ×  7^3 , aquí el número de dígitos en el número es cuatro (1, 0, 2 y 9) que es estrictamente mayor que el número de dígitos de su descomposición en factores primos que es tres (3, 7 y 3).

Los primeros números frugales son: 125, 128, 243, 256, 343, 512, 625, 729, ….
Cabe señalar aquí que los números primos no son números frugales, ya que el número de dígitos en la descomposición en factores primos de un número primo es igual al número de dígitos en el número primo (ya que no se consideran exponentes de valor 1). 
Ejemplo 19 =  19^1 , pero el 1 en el exponente no contribuye al número de dígitos en la factorización prima del número. Por lo tanto, el número de dígitos en el número es dos (1 y 9), que es igual al número de dígitos en su descomposición en factores primos (1 y 9).
Un programa para encontrar si un número, ‘n’, es frugal o no implica pasos simples. Primero, encontramos todos los números primos hasta ‘n’ y luego encontramos la descomposición en factores primos de n. Finalmente, verificamos si el número de dígitos en n es mayor que el número de dígitos en la factorización prima de n.
 

C++

// Program to check for Frugal number
#include <bits/stdc++.h>
using namespace std;
 
// Finding primes upto entered number
vector<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 n
int 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 not
bool 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 number
int 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 number
import 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 number
def 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 n
def countDigits(n):
 
    temp = n;
    c = 0;
    while (temp != 0):
        temp = int(temp / 10);
        c += 1;
    return c;
 
# Checking whether a number is
# Frugal or not
def 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 Code
n = 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 number
using 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 number
function 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 n
function countDigits($n)
{
    $temp = $n;
    $c = 0;
    while ($temp != 0)
    {
        $temp = intval($temp / 10);
        $c++;
    }
    return $c;
}
 
// Checking whether a
// number is Frugal or not
function 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 number
function 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 n
function 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 not
function 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 number
var n = 343;
if (frugal(n))
    document.write( "A Frugal number");
else
    document.write( "Not a frugal number");
 
// This code is contributed by rrrtnx.
</script>
Producción: 

A Frugal number

 

Complejidad de tiempo: O(nlog(logn)) 
Espacio auxiliar: O(n)

Sugiera si alguien tiene una mejor solución que sea más eficiente en términos de espacio y tiempo.
Este artículo es una contribución de Aarti_Rathi . Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.

Optimización: 
el código anterior se puede optimizar usando el enfoque discutido en Imprimir todos los factores primos y sus poderes
 

Publicación traducida automáticamente

Artículo escrito por SaagnikAdhikary 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 *