Dados dos números enteros L y R , la tarea de encontrar el número de números primos dobles en el rango.
Un número N se llama doble primo cuando la cuenta de números primos en el rango de 1 a N (excluyendo 1 e incluyendo N) también es primo.
Ejemplos:
Entrada: L = 3, R = 10
Salida: 4
Explicación:
Para 3, tenemos el rango 1, 2, 3, y el número primo es 2 (que también es un número primo).
Para 4, tenemos el rango 1, 2, 3, 4, y la cuenta de un número primo es 2 (que también es un número primo).
Para 5, tenemos el rango 1, 2, 3, 4, 5, y la cuenta de un número primo es 3 (que también es un número primo).
Para 6, tenemos el rango 1, 2, 3, 4, 5, 6, y la cantidad de números primos es 3 (que también es un número primo).
Para 7, tenemos el rango 1, 2, 3, 4, 5, 6, 7, y el recuento de números primos es 4, que no es primo.
De manera similar, para otros números hasta R = 10, el conteo de números primos no es primo. Por lo tanto, la cuenta de números primos dobles es 4.
Entrada: L = 4, R = 12
Salida: 5
Explicación:
Para el rango dado hay un total de 5 números primos dobles.
Planteamiento:
Para resolver el problema mencionado anteriormente utilizaremos el concepto de Sieve para generar números primos.
- Genere todos los números primos del 0 al 10 6 y guárdelos en una array.
- Inicialice un conteo variable para mantener un registro de números primos desde 1 hasta alguna i-ésima posición.
- Luego, para cada número primo, incrementaremos el conteo y también estableceremos dp[contar] = 1 (donde dp es la array que almacena un número primo doble) indicando el número de números desde 1 hasta alguna i-ésima posición que son primos.
- Por último, encuentre la suma acumulada de la array dp para que la respuesta sea dp[R] – dp[L – 1] .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to find the count
// of Double Prime numbers
// in the range L to R
#include <bits/stdc++.h>
using namespace std;
// Array to make Sieve
// where arr[i]=0 indicates
// non prime and arr[i] = 1
// indicates prime
int arr[1000001];
// Array to find double prime
int dp[1000001];
// Function to find the number
// double prime numbers in range
void count()
{
int maxN = 1000000, i, j;
// Assume all numbers as prime
for (i = 0; i < maxN; i++)
arr[i] = 1;
arr[0] = 0;
arr[1] = 0;
for (i = 2; i * i <= maxN; i++) {
// Check if the number is prime
if (arr[i] == 1) {
// check for multiples of i
for (j = 2 * i; j <= maxN; j += i) {
// Make all multiples of
// ith prime as non-prime
arr[j] = 0;
}
}
}
int cnt = 0;
for (i = 0; i <= maxN; i++) {
// Check if number at ith position
// is prime then increment count
if (arr[i] == 1)
cnt++;
if (arr[cnt] == 1)
// Indicates count of numbers
// from 1 to i that are
// also prime and
// hence double prime
dp[i] = 1;
else
// If number is not a double prime
dp[i] = 0;
}
for (i = 1; i <= maxN; i++)
// finding cumulative sum
dp[i] += dp[i - 1];
}
// Driver code
int main()
{
int L = 4, R = 12;
count();
cout << dp[R] - dp[L - 1];
return 0;
}
Java
// Java program to find the count
// of Double Prime numbers
// in the range L to R
import java.util.*;
import java.lang.*;
class GFG{
// Array to make Sieve
// where arr[i]=0 indicates
// non prime and arr[i] = 1
// indicates prime
static int[] arr = new int[1000001];
// Array to find double prime
static int[] dp = new int[1000001];
// Function to find the number
// double prime numbers in range
static void count()
{
int maxN = 1000000, i, j;
// Assume all numbers as prime
for (i = 0; i < maxN; i++)
arr[i] = 1;
arr[0] = 0;
arr[1] = 0;
for (i = 2; i * i <= maxN; i++)
{
// Check if the number is prime
if (arr[i] == 1)
{
// check for multiples of i
for (j = 2 * i; j <= maxN; j += i)
{
// Make all multiples of
// ith prime as non-prime
arr[j] = 0;
}
}
}
int cnt = 0;
for (i = 0; i <= maxN; i++)
{
// Check if number at ith position
// is prime then increment count
if (arr[i] == 1)
cnt++;
if (arr[cnt] == 1)
// Indicates count of numbers
// from 1 to i that are
// also prime and
// hence double prime
dp[i] = 1;
else
// If number is not a double prime
dp[i] = 0;
}
for (i = 1; i <= maxN; i++)
// finding cumulative sum
dp[i] += dp[i - 1];
}
// Driver code
public static void main(String[] args)
{
int L = 4, R = 12;
count();
System.out.println(dp[R] - dp[L - 1]);
}
}
// This code is contributed by offbeat
Python3
# Python3 program to find the count # of Double Prime numbers # in the range L to R # Array to make Sieve # where arr[i]=0 indicates # non prime and arr[i] = 1 # indicates prime arr = [0] * 1000001 # Array to find double prime dp = [0] * 1000001 # Function to find the number # double prime numbers in range def count(): maxN = 1000000 # Assume all numbers as prime for i in range(0, maxN): arr[i] = 1 arr[0] = 0 arr[1] = 0 i = 2 while(i * i <= maxN): # Check if the number is prime if (arr[i] == 1): # Check for multiples of i for j in range(2 * i, maxN + 1, i): # Make all multiples of # ith prime as non-prime arr[j] = 0 i += 1 cnt = 0 for i in range(0, maxN + 1): # Check if number at ith position # is prime then increment count if (arr[i] == 1): cnt += 1 if (arr[cnt] == 1): # Indicates count of numbers # from 1 to i that are # also prime and # hence double prime dp[i] = 1 else: # If number is not a double prime dp[i] = 0 for i in range(0, maxN + 1): # Finding cumulative sum dp[i] += dp[i - 1] # Driver code L = 4 R = 12 count() print(dp[R] - dp[L - 1]) # This code is contributed by sanjoy_62
C#
// C# program to find the count
// of Double Prime numbers
// in the range L to R
using System;
class GFG{
// Array to make Sieve
// where arr[i]=0 indicates
// non prime and arr[i] = 1
// indicates prime
static int[] arr = new int[1000001];
// Array to find double prime
static int[] dp = new int[1000001];
// Function to find the number
// double prime numbers in range
static void count()
{
int maxN = 1000000, i, j;
// Assume all numbers as prime
for (i = 0; i < maxN; i++)
arr[i] = 1;
arr[0] = 0;
arr[1] = 0;
for (i = 2; i * i <= maxN; i++)
{
// Check if the number is prime
if (arr[i] == 1)
{
// check for multiples of i
for (j = 2 * i; j <= maxN; j += i)
{
// Make all multiples of
// ith prime as non-prime
arr[j] = 0;
}
}
}
int cnt = 0;
for (i = 0; i <= maxN; i++)
{
// Check if number at ith position
// is prime then increment count
if (arr[i] == 1)
cnt++;
if (arr[cnt] == 1)
// Indicates count of numbers
// from 1 to i that are
// also prime and
// hence double prime
dp[i] = 1;
else
// If number is not a double prime
dp[i] = 0;
}
for (i = 1; i <= maxN; i++)
// finding cumulative sum
dp[i] += dp[i - 1];
}
// Driver code
public static void Main()
{
int L = 4, R = 12;
count();
Console.Write(dp[R] - dp[L - 1]);
}
}
// This code is contributed by Code_Mech
Javascript
<script>
// Javascript program to find the count
// of Double Prime numbers
// in the range L to R
// Array to make Sieve
// where arr[i]=0 indicates
// non prime and arr[i] = 1
// indicates prime
let arr = [];
// Array to find double prime
let dp = [];
// Function to find the number
// double prime numbers in range
function count()
{
let maxN = 1000000, i, j;
// Assume all numbers as prime
for (i = 0; i < maxN; i++)
arr[i] = 1;
arr[0] = 0;
arr[1] = 0;
for (i = 2; i * i <= maxN; i++)
{
// Check if the number is prime
if (arr[i] == 1)
{
// check for multiples of i
for (j = 2 * i; j <= maxN; j += i)
{
// Make all multiples of
// ith prime as non-prime
arr[j] = 0;
}
}
}
let cnt = 0;
for (i = 0; i <= maxN; i++)
{
// Check if number at ith position
// is prime then increment count
if (arr[i] == 1)
cnt++;
if (arr[cnt] == 1)
// Indicates count of numbers
// from 1 to i that are
// also prime and
// hence double prime
dp[i] = 1;
else
// If number is not a double prime
dp[i] = 0;
}
for (i = 1; i <= maxN; i++)
// finding cumulative sum
dp[i] += dp[i - 1];
}
// Driver code
let L = 4, R = 12;
count();
document.write(dp[R] - dp[L - 1]);
// This code is contributed by susmitakundugoaldanga.
</script>
Producción:
5
Publicación traducida automáticamente
Artículo escrito por mridulkumar y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA