Dado un rango, la tarea es encontrar el conteo de los números en el rango dado tal que la suma de su dígito sea igual a la suma de todos los dígitos de sus factores primos.
Ejemplos:
Input: l = 2, r = 10 Output: 5 2, 3, 4, 5 and 7 are such numbers Input: l = 15, r = 22 Output: 3 17, 19 and 22 are such numbers As, 17 and 19 are already prime. Prime Factors of 22 = 2 * 11 i.e For 22, Sum of digits is 2+2 = 4 For 2 * 11, Sum of digits is 2 + 1 + 1 = 4
Enfoque: Una solución eficiente es modificar la Criba de Eratóstenes de modo que para cada número no primo almacene el factor primo más pequeño (prefactor).
- Preprocesar para encontrar el factor primo más pequeño para todos los números entre 2 y MAXN. Esto se puede hacer descomponiendo el número en sus factores primos en tiempo constante porque para cada número, si es primo, no tiene prefactor.
- De lo contrario, podemos dividirlo en un factor primo y la otra parte del número que puede ser primo o no.
- Y repita este proceso de extracción de factores hasta que se convierta en un número primo.
- Luego verifique si los dígitos de ese número son iguales a los dígitos de los factores primos sumando los dígitos del factor primo más pequeño, es decir
Suma_dígitos de SPF[n] + Suma_dígitos de (n / SPF[n])
- Ahora haga una array de suma de prefijos que cuente cuántos números válidos hay hasta un número N. Para cada consulta, imprima:
respuesta[R] – respuesta[L-1]
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to Find the count of the numbers
// in the given range such that the sum of its
// digit is equal to the sum of all its prime
// factors digits sum.
#include <bits/stdc++.h>
using namespace std;
// maximum size of number
#define MAXN 100005
// array to store smallest prime factor of number
int spf[MAXN] = { 0 };
// array to store sum of digits of a number
int sum_digits[MAXN] = { 0 };
// boolean array to check given number is countable
// for required answer or not.
bool isValid[MAXN] = { 0 };
// prefix array to store answer
int ans[MAXN] = { 0 };
// Calculating SPF (Smallest Prime Factor) for every
// number till MAXN.
void Smallest_prime_factor()
{
// marking smallest prime factor for every
// number to be itself.
for (int i = 1; i < MAXN; i++)
spf[i] = i;
// separately marking spf for every even
// number as 2
for (int i = 4; i < MAXN; i += 2)
spf[i] = 2;
for (int i = 3; i * i <= MAXN; i += 2)
// checking if i is prime
if (spf[i] == i)
// marking SPF for all numbers divisible by i
for (int j = i * i; j < MAXN; j += i)
// marking spf[j] if it is not
// previously marked
if (spf[j] == j)
spf[j] = i;
}
// Function to find sum of digits in a number
int Digit_Sum(int copy)
{
int d = 0;
while (copy) {
d += copy % 10;
copy /= 10;
}
return d;
}
// find sum of digits of all numbers up to MAXN
void Sum_Of_All_Digits()
{
for (int n = 2; n < MAXN; n++) {
// add sum of digits of least
// prime factor and n/spf[n]
sum_digits[n] = sum_digits[n / spf[n]]
+ Digit_Sum(spf[n]);
// if it is valid make isValid true
if (Digit_Sum(n) == sum_digits[n])
isValid[n] = true;
}
// prefix sum to compute answer
for (int n = 2; n < MAXN; n++) {
if (isValid[n])
ans[n] = 1;
ans[n] += ans[n - 1];
}
}
// Driver code
int main()
{
Smallest_prime_factor();
Sum_Of_All_Digits();
// decleartion
int l, r;
// print answer for required range
l = 2, r = 3;
cout << "Valid numbers in the range " << l << " "
<< r << " are " << ans[r] - ans[l - 1] << endl;
// print answer for required range
l = 2, r = 10;
cout << "Valid numbers in the range " << l << " "
<< r << " are " << ans[r] - ans[l - 1] << endl;
return 0;
}
Java
// Java program to Find the count
// of the numbers in the given
// range such that the sum of its
// digit is equal to the sum of
// all its prime factors digits sum.
import java.io.*;
class GFG
{
// maximum size of number
static int MAXN = 100005;
// array to store smallest
// prime factor of number
static int spf[] = new int[MAXN];
// array to store sum
// of digits of a number
static int sum_digits[] = new int[MAXN];
// boolean array to check
// given number is countable
// for required answer or not.
static boolean isValid[] = new boolean[MAXN];
// prefix array to store answer
static int ans[] = new int[MAXN];
// Calculating SPF (Smallest
// Prime Factor) for every
// number till MAXN.
static void Smallest_prime_factor()
{
// marking smallest prime factor
// for every number to be itself.
for (int i = 1; i < MAXN; i++)
spf[i] = i;
// separately marking spf
// for every even number as 2
for (int i = 4; i < MAXN; i += 2)
spf[i] = 2;
for (int i = 3;
i * i <= MAXN; i += 2)
// checking if i is prime
if (spf[i] == i)
// marking SPF for all
// numbers divisible by i
for (int j = i * i;
j < MAXN; j += i)
// marking spf[j] if it
// is not previously marked
if (spf[j] == j)
spf[j] = i;
}
// Function to find sum
// of digits in a number
static int Digit_Sum(int copy)
{
int d = 0;
while (copy > 0)
{
d += copy % 10;
copy /= 10;
}
return d;
}
// find sum of digits of
// all numbers up to MAXN
static void Sum_Of_All_Digits()
{
for (int n = 2; n < MAXN; n++)
{
// add sum of digits of least
// prime factor and n/spf[n]
sum_digits[n] = sum_digits[n / spf[n]]
+ Digit_Sum(spf[n]);
// if it is valid make isValid true
if (Digit_Sum(n) == sum_digits[n])
isValid[n] = true;
}
// prefix sum to compute answer
for (int n = 2; n < MAXN; n++)
{
if (isValid[n])
ans[n] = 1;
ans[n] += ans[n - 1];
}
}
// Driver code
public static void main (String[] args)
{
Smallest_prime_factor();
Sum_Of_All_Digits();
// declaration
int l, r;
// print answer for required range
l = 2; r = 3;
System.out.println("Valid numbers in the range " +
l + " " + r + " are " +
(ans[r] - ans[l - 1] ));
// print answer for required range
l = 2; r = 10;
System.out.println("Valid numbers in the range " +
l + " " + r + " are " +
(ans[r] - ans[l - 1]));
}
}
// This code is contributed
// by Inder
Python 3
# Python 3 program to Find the count of
# the numbers in the given range such
# that the sum of its digit is equal to
# the sum of all its prime factors digits sum.
# maximum size of number
MAXN = 100005
# array to store smallest prime
# factor of number
spf = [0] * MAXN
# array to store sum of digits of a number
sum_digits = [0] * MAXN
# boolean array to check given number
# is countable for required answer or not.
isValid = [0] * MAXN
# prefix array to store answer
ans = [0]*MAXN
# Calculating SPF (Smallest Prime Factor)
# for every number till MAXN.
def Smallest_prime_factor():
# marking smallest prime factor
# for every number to be itself.
for i in range(1, MAXN):
spf[i] = i
# separately marking spf for
# every even number as 2
for i in range(4, MAXN, 2):
spf[i] = 2
i = 3
while i * i <= MAXN:
# checking if i is prime
if (spf[i] == i):
# marking SPF for all numbers
# divisible by i
for j in range(i * i, MAXN, i):
# marking spf[j] if it is not
# previously marked
if (spf[j] == j):
spf[j] = i
i += 2
# Function to find sum of digits
# in a number
def Digit_Sum(copy):
d = 0
while (copy) :
d += copy % 10
copy //= 10
return d
# find sum of digits of all
# numbers up to MAXN
def Sum_Of_All_Digits():
for n in range(2, MAXN) :
# add sum of digits of least
# prime factor and n/spf[n]
sum_digits[n] = (sum_digits[n // spf[n]] +
Digit_Sum(spf[n]))
# if it is valid make isValid true
if (Digit_Sum(n) == sum_digits[n]):
isValid[n] = True
# prefix sum to compute answer
for n in range(2, MAXN) :
if (isValid[n]):
ans[n] = 1
ans[n] += ans[n - 1]
# Driver code
if __name__ == "__main__":
Smallest_prime_factor()
Sum_Of_All_Digits()
# print answer for required range
l = 2
r = 3
print("Valid numbers in the range", l, r,
"are", ans[r] - ans[l - 1])
# print answer for required range
l = 2
r = 10
print("Valid numbers in the range", l, r,
"are", ans[r] - ans[l - 1])
# This code is contributed by ita_c
C#
// C# program to Find the count
// of the numbers in the given
// range such that the sum of its
// digit is equal to the sum of
// all its prime factors digits sum.
using System;
class GFG
{
// maximum size of number
static int MAXN = 100005;
// array to store smallest
// prime factor of number
static int []spf = new int[MAXN];
// array to store sum
// of digits of a number
static int []sum_digits = new int[MAXN];
// boolean array to check
// given number is countable
// for required answer or not.
static bool []isValid = new bool[MAXN];
// prefix array to store answer
static int []ans = new int[MAXN];
// Calculating SPF (Smallest
// Prime Factor) for every
// number till MAXN.
static void Smallest_prime_factor()
{
// marking smallest prime factor
// for every number to be itself.
for (int i = 1; i < MAXN; i++)
spf[i] = i;
// separately marking spf
// for every even number as 2
for (int i = 4; i < MAXN; i += 2)
spf[i] = 2;
for (int i = 3;
i * i <= MAXN; i += 2)
// checking if i is prime
if (spf[i] == i)
// marking SPF for all
// numbers divisible by i
for (int j = i * i;
j < MAXN; j += i)
// marking spf[j] if it
// is not previously marked
if (spf[j] == j)
spf[j] = i;
}
// Function to find sum
// of digits in a number
static int Digit_Sum(int copy)
{
int d = 0;
while (copy > 0)
{
d += copy % 10;
copy /= 10;
}
return d;
}
// find sum of digits of
// all numbers up to MAXN
static void Sum_Of_All_Digits()
{
for (int n = 2; n < MAXN; n++)
{
// add sum of digits of least
// prime factor and n/spf[n]
sum_digits[n] = sum_digits[n / spf[n]] +
Digit_Sum(spf[n]);
// if it is valid make
// isValid true
if (Digit_Sum(n) == sum_digits[n])
isValid[n] = true;
}
// prefix sum to compute answer
for (int n = 2; n < MAXN; n++)
{
if (isValid[n])
ans[n] = 1;
ans[n] += ans[n - 1];
}
}
// Driver code
public static void Main ()
{
Smallest_prime_factor();
Sum_Of_All_Digits();
// declaration
int l, r;
// print answer for required range
l = 2; r = 3;
Console.WriteLine("Valid numbers in the range " +
l + " " + r + " are " +
(ans[r] - ans[l - 1] ));
// print answer for required range
l = 2; r = 10;
Console.WriteLine("Valid numbers in the range " +
l + " " + r + " are " +
(ans[r] - ans[l - 1]));
}
}
// This code is contributed
// by Subhadeep
Javascript
<script>
// Javascript program to Find the count
// of the numbers in the given
// range such that the sum of its
// digit is equal to the sum of
// all its prime factors digits sum.
// maximum size of number
var MAXN = 100005;
// array to store smallest
// prime factor of number
var spf = Array.from({length: MAXN}, (_, i) => 0);
// array to store sum
// of digits of a number
var sum_digits = Array.from({length: MAXN}, (_, i) => 0);
// boolean array to check
// given number is countable
// for required answer or not.
var isValid = Array.from({length: MAXN}, (_, i) => false);
// prefix array to store answer
var ans = Array.from({length: MAXN}, (_, i) => 0);
// Calculating SPF (Smallest
// Prime Factor) for every
// number till MAXN.
function Smallest_prime_factor()
{
// marking smallest prime factor
// for every number to be itself.
for (i = 1; i < MAXN; i++)
spf[i] = i;
// separately marking spf
// for every even number as 2
for (i = 4; i < MAXN; i += 2)
spf[i] = 2;
for (i = 3;
i * i <= MAXN; i += 2)
// checking if i is prime
if (spf[i] == i)
// marking SPF for all
// numbers divisible by i
for (j = i * i;
j < MAXN; j += i)
// marking spf[j] if it
// is not previously marked
if (spf[j] == j)
spf[j] = i;
}
// Function to find sum
// of digits in a number
function Digit_Sum(copy)
{
var d = 0;
while (copy > 0)
{
d += copy % 10;
copy = parseInt(copy/10);
}
return d;
}
// find sum of digits of
// all numbers up to MAXN
function Sum_Of_All_Digits()
{
for (n = 2; n < MAXN; n++)
{
// add sum of digits of least
// prime factor and n/spf[n]
sum_digits[n] = sum_digits[parseInt(n / spf[n])]
+ Digit_Sum(spf[n]);
// if it is valid make isValid true
if (Digit_Sum(n) == sum_digits[n])
isValid[n] = true;
}
// prefix sum to compute answer
for (n = 2; n < MAXN; n++)
{
if (isValid[n])
ans[n] = 1;
ans[n] += ans[n - 1];
}
}
// Driver code
Smallest_prime_factor();
Sum_Of_All_Digits();
// declaration
var l, r;
// print answer for required range
l = 2; r = 3;
document.write("Valid numbers in the range " +
l + " " + r + " are " +
(ans[r] - ans[l - 1] ));
// print answer for required range
l = 2; r = 10;
document.write("<br>Valid numbers in the range " +
l + " " + r + " are " +
(ans[r] - ans[l - 1]));
// This code contributed by shikhasingrajput
</script>
Producción:
Valid numbers in the range 2 3 are 2 Valid numbers in the range 2 10 are 5
Publicación traducida automáticamente
Artículo escrito por pawan_asipu y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA