Un número N se llama Número derrochador si el número de dígitos en la descomposición en factores primos de N (incluidas las potencias) es mayor que el número de dígitos en N. Todos los números primos son derrochadores.
Por ejemplo, 52 es un número derrochador ya que su descomposición en factores primos es 2*2*13 , y su descomposición en factores primos tiene un total de cuatro dígitos (1, 2, 2, 3) que es más que el número total de dígitos en 52.
Los primeros números derrochadores son:
4, 6, 8, 9, 12, 18, 20, 22, 24,…
Programa para imprimir números derrochadores menores o iguales al número dado N
Dado un número N , la tarea es imprimir Números derrochadores menores o iguales a N .
Ejemplos:
Entrada: N = 10
Salida: 4, 6, 8, 9
Entrada: N = 12
Salida: 4, 6, 8, 9, 12
Acercarse:
- Cuente todos los números primos hasta 10 6 usando Sieve of Sundaram .
- Encuentre el número de dígitos en N .
- Encuentre todos los factores primos de N y haga lo siguiente para cada factor primo p :
- Encuentre el número de dígitos en p .
- Cuente la potencia más alta de p que divide a N.
- Encuentra la suma de los dos anteriores.
- Si los dígitos de los factores primos son más que los dígitos del número original, devuelve verdadero. De lo contrario, devuelve falso.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#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;
// Function for Sieve of Sundaram
void sieveSundaram()
{
// Boolean Array
bool marked[MAX / 2 + 1] = { 0 };
// Mark all numbers which do not
// generate prime number by 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 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 that returns true if n
// is a Wasteful number
bool isWasteful(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;
}
int pDigit = 0, count_exp = 0, p;
// Count all digits in prime factors of N
// pDigit is going to hold this value.
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 more than
// digits in original number then
// return true. Else return false.
return (pDigit > sumDigits);
}
// Function to print Wasteful Number before N
void Solve(int N)
{
// Iterate till N and check if i
// is wastefull or not
for (int i = 1; i < N; i++) {
if (isWasteful(i)) {
cout << i << " ";
}
}
}
// Driver code
int main()
{
// Precompute prime numbers upto 10^6
sieveSundaram();
int N = 10;
// Function Call
Solve(N);
return 0;
}
Java
// Java program for the above approach
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>();
// Function for Sieve of Sundaram
static void sieveSundaram()
{
// Boolean Array
boolean marked[] = new boolean[MAX / 2 + 1];
// Mark all numbers which do not
// generate prime number by 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 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 that returns true if n
// is a Wasteful number
static boolean isWasteful(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;
}
int pDigit = 0, count_exp = 0, p = 0;
// Count all digits in prime factors of N
// pDigit is going to hold this value.
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 more than
// digits in original number then
// return true. Else return false.
return (pDigit > sumDigits);
}
// Function to print Wasteful Number before N
static void Solve(int N)
{
// Iterate till N and check if i
// is wastefull or not
for (int i = 1; i < N; i++)
{
if (isWasteful(i))
{
System.out.print(i + " ");
}
}
}
// Driver code
public static void main(String[] args)
{
// Precompute prime numbers upto 10^6
sieveSundaram();
int N = 10;
// Function Call
Solve(N);
}
}
// This code is contributed by 29AjayKumar
Python3
# Python3 program for the # above approach import math MAX = 10000 # Array to store all prime # less than and equal to MAX. primes = [] # Function for Sieve of # Sundaram def sieveSundaram(): # Boolean Array marked = [False] * ((MAX // 2) + 1) # Mark all numbers which do not # generate prime number by 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) # Print 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 that returns true if n # is a Wasteful number def isWasteful(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 pDigit, count_exp, p = 0, 0, 0 # Count all digits in prime # factors of N pDigit is going # to hold this value. i = 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 # 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 i += 1 # 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 more than digits in # original number then return # true. Else return false. return bool(pDigit > sumDigits) # Function to print Wasteful Number # before N def Solve(N): # Iterate till N and check # if i is wastefull or not for i in range(1, N): if (isWasteful(i)): print(i, end = " ") # Driver code # Precompute prime numbers # upto 10^6 sieveSundaram() N = 10 # Function Call Solve(N) # This code is contributed by divyeshrabadiya07
C#
// C# program for the above approach
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>();
// Function for Sieve of Sundaram
static void sieveSundaram()
{
// Boolean Array
bool []marked = new bool[MAX / 2 + 1];
// Mark all numbers which do not
// generate prime number by 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 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 that returns true if n
// is a Wasteful number
static bool isWasteful(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;
}
int pDigit = 0, count_exp = 0, p = 0;
// Count all digits in prime factors of N
// pDigit is going to hold this value.
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 more than
// digits in original number then
// return true. Else return false.
return (pDigit > sumDigits);
}
// Function to print Wasteful Number before N
static void Solve(int N)
{
// Iterate till N and check if i
// is wastefull or not
for (int i = 1; i < N; i++)
{
if (isWasteful(i))
{
Console.Write(i + " ");
}
}
}
// Driver code
public static void Main(String[] args)
{
// Precompute prime numbers upto 10^6
sieveSundaram();
int N = 10;
// Function Call
Solve(N);
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// Javascript implementation for the above approach
let MAX = 10000;
// Array to store all prime less
// than and equal to MAX.
let primes = [];
// Function for Sieve of Sundaram
function sieveSundaram()
{
// Boolean Array
let marked = Array.from({length: MAX / 2 + 1},
(_, i) => 0);
// Mark all numbers which do not
// generate prime number by 2*i+1
for (let i = 1;
i <= Math.floor((Math.sqrt(MAX) - 1) / 2);
i++)
{
for (let j = (i * (i + 1)) << 1;
j <= Math.floor(MAX / 2);
j = j + 2 * i + 1)
{
marked[j] = true;
}
}
// Since 2 is a prime number
primes.push(2);
// Print remaining primes are of the
// form 2*i + 1 such that marked[i]
// is false.
for (let i = 1; i <= Math.floor(MAX / 2); i++)
if (marked[i] == false)
primes.push(2 * i + 1);
}
// Function that returns true if n
// is a Wasteful number
function isWasteful(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);
}
let pDigit = 0, count_exp = 0, p = 0;
// Count all digits in prime factors of N
// pDigit is going to hold this value.
for (let i = 0; primes[i] <= Math.floor(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 = Math.floor(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 more than
// digits in original number then
// return true. Else return false.
return (pDigit > sumDigits);
}
// Function to print Wasteful Number before N
function Solve(N)
{
// Iterate till N and check if i
// is wastefull or not
for (let i = 1; i < N; i++)
{
if (isWasteful(i))
{
document.write(i + " ");
}
}
}
// Driver Code
// Precompute prime numbers upto 10^6
sieveSundaram();
let N = 10;
// Function Call
Solve(N);
</script>
Producción:
4 6 8 9
Complejidad de tiempo: O(N*log(log N))
Referencia: https://oeis.org/A046760