Dado el rango L y R, cuente todos los números entre L y R de modo que la suma de los dígitos de cada número y la suma de los cuadrados de los dígitos de cada número sea primo .
Nota: 10 <= [L, R] <= 10 8
Ejemplos:
Entrada: L = 10, R = 20
Salida: 4
Estos tipos de números son: 11 12 14 16Entrada: L = 100, R = 130
Salida: 9
Estos tipos de números son: 101 102 104 106 110 111 113 119 120
Enfoque ingenuo:
solo obtenga la suma de los dígitos de cada número y la suma del cuadrado de los dígitos de cada número y verifique si ambos son primos o no.
Enfoque eficiente:
- Ahora, si observa detenidamente el rango, el número es 10 8 , es decir, y el número más grande menor que este será 99999999 , y el número máximo que se puede formar es 8 * ( 9 * 9 ) = 648 (como el la suma de los cuadrados de los dígitos es 9 2 + 9 2 + … 8 veces,) por lo tanto, solo necesitamos números primos hasta 648, lo que se puede hacer usando la criba de Eratóstenes.
- Ahora itere para cada número en el rango y verifique si cumple con las condiciones anteriores o no.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
// Sieve of prime numbers
void primesieve(vector<bool>& prime)
{
// Sieve to store whether a
// number is prime or not in
// O(nlog(log(n)))
prime[1] = false;
for (int p = 2; p * p <= 650; p++) {
if (prime[p] == true) {
for (int i = p * 2; i <= 650; i += p)
prime[i] = false;
}
}
}
// Function to return sum of digit
// and sum of square of digit
pair<int, int> sum_sqsum(int n)
{
int sum = 0;
int sqsum = 0;
int x;
// Until number is not
// zero
while (n) {
x = n % 10;
sum += x;
sqsum += x * x;
n /= 10;
}
return (make_pair(sum, sqsum));
}
// Function to return the count
// of number form L to R
// whose sum of digits and
// sum of square of digits
// are prime
int countnumber(int L, int R)
{
vector<bool> prime(651, true);
primesieve(prime);
int cnt = 0;
// Iterate for each value
// in the range of L to R
for (int i = L; i <= R; i++) {
// digit.first stores sum of digits
// digit.second stores sum of
// square of digit
pair<int, int> digit = sum_sqsum(i);
// If sum of digits and sum of
// square of digit both are
// prime then increment the count
if (prime[digit.first]
&& prime[digit.second]) {
cnt += 1;
}
}
return cnt;
}
// Driver Code
int main()
{
int L = 10;
int R = 20;
cout << countnumber(L, R);
}
Java
// Java implementation of the approach
import java.util.*;
class GFG
{
static class pair
{
int first, second;
public pair(int first, int second)
{
this.first = first;
this.second = second;
}
}
// Sieve of prime numbers
static void primesieve(boolean []prime)
{
// Sieve to store whether a
// number is prime or not in
// O(nlog(log(n)))
prime[1] = false;
for (int p = 2; p * p <= 650; p++)
{
if (prime[p] == true)
{
for (int i = p * 2; i <= 650; i += p)
prime[i] = false;
}
}
}
// Function to return sum of digit
// and sum of square of digit
static pair sum_sqsum(int n)
{
int sum = 0;
int sqsum = 0;
int x;
// Until number is not
// zero
while (n > 0)
{
x = n % 10;
sum += x;
sqsum += x * x;
n /= 10;
}
return (new pair(sum, sqsum));
}
// Function to return the count
// of number form L to R
// whose sum of digits and
// sum of square of digits
// are prime
static int countnumber(int L, int R)
{
boolean []prime = new boolean[651];
Arrays.fill(prime, true);
primesieve(prime);
int cnt = 0;
// Iterate for each value
// in the range of L to R
for (int i = L; i <= R; i++)
{
// digit.first stores sum of digits
// digit.second stores sum of
// square of digit
pair digit = sum_sqsum(i);
// If sum of digits and sum of
// square of digit both are
// prime then increment the count
if (prime[digit.first] &&
prime[digit.second])
{
cnt += 1;
}
}
return cnt;
}
// Driver Code
public static void main(String[] args)
{
int L = 10;
int R = 20;
System.out.println(countnumber(L, R));
}
}
// This code is contributed by PrinciRaj1992
Python3
# Python3 implementation of the approach from math import sqrt # Sieve of prime numbers def primesieve(prime) : # Sieve to store whether a # number is prime or not in # O(nlog(log(n))) prime[1] = False; for p in range(2, int(sqrt(650)) + 1) : if (prime[p] == True) : for i in range(p * 2, 651, p) : prime[i] = False; # Function to return sum of digit # and sum of square of digit def sum_sqsum(n) : sum = 0; sqsum = 0; # Until number is not # zero while (n) : x = n % 10; sum += x; sqsum += x * x; n //= 10; return (sum, sqsum); # Function to return the count # of number form L to R # whose sum of digits and # sum of square of digits # are prime def countnumber(L, R): prime = [True] * 651; primesieve(prime); cnt = 0; # Iterate for each value # in the range of L to R for i in range(L, R + 1) : # digit.first stores sum of digits # digit.second stores sum of # square of digit digit = sum_sqsum(i); # If sum of digits and sum of # square of digit both are # prime then increment the count if (prime[digit[0]] and prime[digit[1]]) : cnt += 1; return cnt; # Driver Code if __name__ == "__main__" : L = 10; R = 20; print(countnumber(L, R)); # This code is contributed by AnkitRai01
C#
// C# implementation of the approach
using System;
class GFG
{
public class pair
{
public int first, second;
public pair(int first, int second)
{
this.first = first;
this.second = second;
}
}
// Sieve of prime numbers
static void primesieve(bool []prime)
{
// Sieve to store whether a
// number is prime or not in
// O(nlog(log(n)))
prime[1] = false;
for (int p = 2; p * p <= 650; p++)
{
if (prime[p] == true)
{
for (int i = p * 2;
i <= 650; i += p)
prime[i] = false;
}
}
}
// Function to return sum of digit
// and sum of square of digit
static pair sum_sqsum(int n)
{
int sum = 0;
int sqsum = 0;
int x;
// Until number is not
// zero
while (n > 0)
{
x = n % 10;
sum += x;
sqsum += x * x;
n /= 10;
}
return (new pair(sum, sqsum));
}
// Function to return the count
// of number form L to R
// whose sum of digits and
// sum of square of digits
// are prime
static int countnumber(int L, int R)
{
bool []prime = new bool[651];
for (int i = 0; i < 651; i++)
prime[i] = true;
primesieve(prime);
int cnt = 0;
// Iterate for each value
// in the range of L to R
for (int i = L; i <= R; i++)
{
// digit.first stores sum of digits
// digit.second stores sum of
// square of digit
pair digit = sum_sqsum(i);
// If sum of digits and sum of
// square of digit both are
// prime then increment the count
if (prime[digit.first] &&
prime[digit.second])
{
cnt += 1;
}
}
return cnt;
}
// Driver Code
public static void Main(String[] args)
{
int L = 10;
int R = 20;
Console.WriteLine(countnumber(L, R));
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// Javascript implementation of the approach
// Sieve of prime numbers
function primesieve(prime) {
// Sieve to store whether a
// number is prime or not in
// O(nlog(log(n)))
prime[1] = false;
for (let p = 2; p < Math.floor(Math.sqrt(650)) + 1; p++) {
if (prime[p] == true) {
for (let i = p * 2; i < 651; i += p) {
prime[i] = false;
}
}
}
}
// Function to return sum of digit
// and sum of square of digit
function sum_sqsum(n) {
let sum = 0;
let sqsum = 0;
let x;
// Until number is not
// zero
while (n) {
x = n % 10;
sum += x;
sqsum += x * x;
n = Math.floor(n / 10);
}
return [sum, sqsum];
}
// Function to return the count
// of number form L to R
// whose sum of digits and
// sum of square of digits
// are prime
function countnumber(L, R) {
let prime = new Array(651).fill(true);
primesieve(prime);
let cnt = 0;
// Iterate for each value
// in the range of L to R
for (let i = L; i <= R; i++) {
// digit.first stores sum of digits
// digit.second stores sum of
// square of digit
let digit = sum_sqsum(i);
// If sum of digits and sum of
// square of digit both are
// prime then increment the count
if (prime[digit[0]] && prime[digit[1]]) {
cnt += 1;
}
}
return cnt;
}
// Driver Code
let L = 10;
let R = 20;
document.write(countnumber(L, R));
// This code is contributed by _saurabh_jaiswal
</script>
Producción:
4
Nota:
- Almacene todos los números que satisfagan las condiciones anteriores en otra array y utilice la búsqueda binaria para averiguar cuántos elementos de la array son menores que R , digamos cnt1 , y cuántos elementos de la array son menores que L , digamos cnt2 . Retorna cnt1 – cnt2
Tiempo Complejidad: O(log(N))por consulta. - Podemos usar una array de prefijos o un enfoque de DP de modo que ya almacene cuántos no. son buenos del tipo anterior, del índice 0 al i, y devuelven el recuento total dando DP[R] – DP[L-1]
Complejidad de tiempo: O(1) por consulta.
Publicación traducida automáticamente
Artículo escrito por Chandan_Agrawal y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA