Dados dos números enteros L y R , la tarea es encontrar el número total de números primos en el rango [L, R] cuya suma de los dígitos también es un número primo.
Ejemplos:
Entrada: L = 1, R = 10
Salida: 4
Explicación:
Los números primos en el rango L = 1 a R = 10 son {2, 3, 5, 7}.
Su suma de dígitos es {2, 3, 5, 7}.
Dado que todos los números son primos, la respuesta a la consulta es 4.
Entrada: L = 5, R = 20
Salida: 3
Explicación:
los números primos en el rango L = 5 a R = 20 son {5, 7, 11, 13, 17, 19}.1
Su suma de dígitos es {5, 7, 2, 4, 8, 10}.
Solo {5, 7, 2} son primos, por lo que la respuesta a la consulta es 3.
Enfoque ingenuo: el enfoque ingenuo es iterar para cada número en el rango [L, R] y verificar si el número es primo o no. Si el número es primo, encuentre la suma de sus dígitos y verifique nuevamente si la suma es prima o no. Si la suma es prima, entonces incremente el contador para el elemento actual en el rango [L, R] .
Complejidad de tiempo: O((R – L)*log(log P)) donde P es el número primo en el rango [L, R] .
Enfoque eficiente:
- Almacene todos los números primos que van del 1 al 10 6 en una array utilizando la criba de Eratóstenes .
- Cree otra array que almacene si la suma de los dígitos de todos los números del 1 al 10 6 que son primos.
- Ahora, calcule una array de prefijos para almacenar recuentos hasta cada valor antes del límite.
- Una vez que tenemos una array de prefijos, el valor de prefijo[R] – prefijo[L-1] da el conteo de elementos en el rango dado que son primos y cuya suma también es primo.
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;
int maxN = 1000000;
// Create an array for storing primes
int arr[1000001];
// Create a prefix array that will
// contain whether sum is prime or not
int prefix[1000001];
// Function to find primes in the range
// and check whether the sum of digits
// of a prime number is prime or not
void findPrimes()
{
// Initialise Prime array arr[]
for (int i = 1; i <= maxN; i++)
arr[i] = 1;
// Since 0 and 1 are not prime
// numbers we mark them as '0'
arr[0] = 0, arr[1] = 0;
// Using Sieve Of Eratosthenes
for (int i = 2; i * i <= maxN; i++) {
// if the number is prime
if (arr[i] == 1) {
// Mark all the multiples
// of i starting from square
// of i with '0' ie. composite
for (int j = i * i;
j <= maxN; j += i) {
//'0' represents not prime
arr[j] = 0;
}
}
}
// Initialise a sum variable as 0
int sum = 0;
prefix[0] = 0;
for (int i = 1; i <= maxN; i++) {
// Check if the number is prime
if (arr[i] == 1) {
// A temporary variable to
// store the number
int temp = i;
sum = 0;
// Loop to calculate the
// sum of digits
while (temp > 0) {
int x = temp % 10;
sum += x;
temp = temp / 10;
// Check if the sum of prime
// number is prime
if (arr[sum] == 1) {
// if prime mark 1
prefix[i] = 1;
}
else {
// If not prime mark 0
prefix[i] = 0;
}
}
}
}
// computing prefix array
for (int i = 1; i <= maxN; i++) {
prefix[i]
+= prefix[i - 1];
}
}
// Function to count the prime numbers
// in the range [L, R]
void countNumbersInRange(int l, int r)
{
// Function Call to find primes
findPrimes();
int result = prefix[r]
- prefix[l - 1];
// Print the result
cout << result << endl;
}
// Driver Code
int main()
{
// Input range
int l, r;
l = 5, r = 20;
// Function Call
countNumbersInRange(l, r);
return 0;
}
Java
// Java program for the above approach
class GFG{
static int maxN = 1000000;
// Create an array for storing primes
static int []arr = new int[1000001];
// Create a prefix array that will
// contain whether sum is prime or not
static int []prefix = new int[1000001];
// Function to find primes in the range
// and check whether the sum of digits
// of a prime number is prime or not
static void findPrimes()
{
// Initialise Prime array arr[]
for (int i = 1; i <= maxN; i++)
arr[i] = 1;
// Since 0 and 1 are not prime
// numbers we mark them as '0'
arr[0] = 0;
arr[1] = 0;
// Using Sieve Of Eratosthenes
for (int i = 2; i * i <= maxN; i++)
{
// if the number is prime
if (arr[i] == 1)
{
// Mark all the multiples
// of i starting from square
// of i with '0' ie. composite
for (int j = i * i;
j <= maxN; j += i)
{
//'0' represents not prime
arr[j] = 0;
}
}
}
// Initialise a sum variable as 0
int sum = 0;
prefix[0] = 0;
for (int i = 1; i <= maxN; i++)
{
// Check if the number is prime
if (arr[i] == 1)
{
// A temporary variable to
// store the number
int temp = i;
sum = 0;
// Loop to calculate the
// sum of digits
while (temp > 0)
{
int x = temp % 10;
sum += x;
temp = temp / 10;
// Check if the sum of prime
// number is prime
if (arr[sum] == 1)
{
// if prime mark 1
prefix[i] = 1;
}
else
{
// If not prime mark 0
prefix[i] = 0;
}
}
}
}
// computing prefix array
for (int i = 1; i <= maxN; i++)
{
prefix[i] += prefix[i - 1];
}
}
// Function to count the prime numbers
// in the range [L, R]
static void countNumbersInRange(int l, int r)
{
// Function Call to find primes
findPrimes();
int result = prefix[r] - prefix[l - 1];
// Print the result
System.out.print(result + "\n");
}
// Driver Code
public static void main(String[] args)
{
// Input range
int l, r;
l = 5;
r = 20;
// Function Call
countNumbersInRange(l, r);
}
}
// This code is contributed by sapnasingh4991
Python3
# Python3 program for the above approach maxN = 1000000 # Create an array for storing primes arr = [0] * (1000001) # Create a prefix array that will # contain whether sum is prime or not prefix = [0] * (1000001) # Function to find primes in the range # and check whether the sum of digits # of a prime number is prime or not def findPrimes(): # Initialise Prime array arr[] for i in range(1, maxN + 1): arr[i] = 1 # Since 0 and 1 are not prime # numbers we mark them as '0' arr[0] = 0 arr[1] = 0 # Using Sieve Of Eratosthenes i = 2 while i * i <= maxN: # If the number is prime if (arr[i] == 1): # Mark all the multiples # of i starting from square # of i with '0' ie. composite for j in range(i * i, maxN, i): # '0' represents not prime arr[j] = 0 i += 1 # Initialise a sum variable as 0 sum = 0 prefix[0] = 0 for i in range(1, maxN + 1): # Check if the number is prime if (arr[i] == 1): # A temporary variable to # store the number temp = i sum = 0 # Loop to calculate the # sum of digits while (temp > 0): x = temp % 10 sum += x temp = temp // 10 # Check if the sum of prime # number is prime if (arr[sum] == 1): # If prime mark 1 prefix[i] = 1 else: # If not prime mark 0 prefix[i] = 0 # Computing prefix array for i in range(1, maxN + 1): prefix[i] += prefix[i - 1] # Function to count the prime numbers # in the range [L, R] def countNumbersInRange(l, r): # Function call to find primes findPrimes() result = (prefix[r] - prefix[l - 1]) # Print the result print(result) # Driver Code if __name__ == "__main__": # Input range l = 5 r = 20 # Function call countNumbersInRange(l, r) # This code is contributed by chitranayal
C#
// C# program for the above approach
using System;
class GFG{
static int maxN = 1000000;
// Create an array for storing primes
static int []arr = new int[1000001];
// Create a prefix array that will
// contain whether sum is prime or not
static int []prefix = new int[1000001];
// Function to find primes in the range
// and check whether the sum of digits
// of a prime number is prime or not
static void findPrimes()
{
// Initialise Prime array arr[]
for (int i = 1; i <= maxN; i++)
arr[i] = 1;
// Since 0 and 1 are not prime
// numbers we mark them as '0'
arr[0] = 0;
arr[1] = 0;
// Using Sieve Of Eratosthenes
for (int i = 2; i * i <= maxN; i++)
{
// if the number is prime
if (arr[i] == 1)
{
// Mark all the multiples
// of i starting from square
// of i with '0' ie. composite
for (int j = i * i;
j <= maxN; j += i)
{
//'0' represents not prime
arr[j] = 0;
}
}
}
// Initialise a sum variable as 0
int sum = 0;
prefix[0] = 0;
for (int i = 1; i <= maxN; i++)
{
// Check if the number is prime
if (arr[i] == 1)
{
// A temporary variable to
// store the number
int temp = i;
sum = 0;
// Loop to calculate the
// sum of digits
while (temp > 0)
{
int x = temp % 10;
sum += x;
temp = temp / 10;
// Check if the sum of prime
// number is prime
if (arr[sum] == 1)
{
// if prime mark 1
prefix[i] = 1;
}
else
{
// If not prime mark 0
prefix[i] = 0;
}
}
}
}
// computing prefix array
for (int i = 1; i <= maxN; i++)
{
prefix[i] += prefix[i - 1];
}
}
// Function to count the prime numbers
// in the range [L, R]
static void countNumbersInRange(int l, int r)
{
// Function Call to find primes
findPrimes();
int result = prefix[r] - prefix[l - 1];
// Print the result
Console.Write(result + "\n");
}
// Driver Code
public static void Main()
{
// Input range
int l, r;
l = 5;
r = 20;
// Function Call
countNumbersInRange(l, r);
}
}
// This code is contributed by Code_Mech
Javascript
<script>
// Javascript implementation for the above approach
let maxN = 1000000;
// Create an array for storing primes
let arr = Array.from({length: 1000001}, (_, i) => 0);
// Create a prefix array that will
// contain whether sum is prime or not
let prefix = Array.from({length: 1000001}, (_, i) => 0);
// Function to find primes in the range
// and check whether the sum of digits
// of a prime number is prime or not
function findPrimes()
{
// Initialise Prime array arr[]
for (let i = 1; i <= maxN; i++)
arr[i] = 1;
// Since 0 and 1 are not prime
// numbers we mark them as '0'
arr[0] = 0;
arr[1] = 0;
// Using Sieve Of Eratosthenes
for (let i = 2; i * i <= maxN; i++)
{
// if the number is prime
if (arr[i] == 1)
{
// Mark all the multiples
// of i starting from square
// of i with '0' ie. composite
for (let j = i * i;
j <= maxN; j += i)
{
//'0' represents not prime
arr[j] = 0;
}
}
}
// Initialise a sum variable as 0
let sum = 0;
prefix[0] = 0;
for (let i = 1; i <= maxN; i++)
{
// Check if the number is prime
if (arr[i] == 1)
{
// A temporary variable to
// store the number
let temp = i;
sum = 0;
// Loop to calculate the
// sum of digits
while (temp > 0)
{
let x = temp % 10;
sum += x;
temp = Math.floor(temp / 10);
// Check if the sum of prime
// number is prime
if (arr[sum] == 1)
{
// if prime mark 1
prefix[i] = 1;
}
else
{
// If not prime mark 0
prefix[i] = 0;
}
}
}
}
// computing prefix array
for (let i = 1; i <= maxN; i++)
{
prefix[i] += prefix[i - 1];
}
}
// Function to count the prime numbers
// in the range [L, R]
function countNumbersInRange(l, r)
{
// Function Call to find primes
findPrimes();
let result = prefix[r] - prefix[l - 1];
// Print the result
document.write(result + "\n");
}
// Driver Code
// Input range
let l, r;
l = 5;
r = 20;
// Function Call
countNumbersInRange(l, r);
</script>
Producción:
3
Complejidad de tiempo: O(N*(log(log)N))
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por guptarashi130999 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA