Dadas consultas Q donde cada consulta consta de dos números enteros positivos L y R y la tarea es encontrar la diferencia absoluta entre el recuento de números primos y el recuento de números compuestos en el rango [L, R]
Ejemplos:
Entrada: consultas[][] = {{1, 10}}
Salida:
2
2, 3, 5 y 7 son los únicos primos en el rango dado.
Entonces, el resto de los 6 enteros son compuestos.
|6 – 4| = 2
Entrada: consultas[][] = {{4, 10}, {5, 30}}
Salida:
3
10
Acercarse:
- Usando la criba de Eratóstenes , genere una array prime[i] tal que prime[i] = 1 si i es primo sino 0 .
- Ahora actualice la array prime[] de modo que prime[i] almacene el recuento de números primos que son ≤ i .
- Para cada consulta, el conteo de números primos en el rango [L, R] se puede encontrar mediante prime[R] – prime[L – 1] , y el conteo de números compuestos será el conteo de números primos restados del elementos totales.
- Imprime la diferencia absoluta entre el conteo de números primos y el conteo de compuestos encontrados en el paso anterior.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
#define MAX 1000000
int prime[MAX + 1];
// Function to update prime[]
// such prime[i] stores the
// count of prime numbers <= i
void updatePrimes()
{
// prime[] marks all prime numbers as true
// so prime[i] = 1 if ith number is a prime
// Initialization
for (int i = 2; i <= MAX; i++) {
prime[i] = 1;
}
// 0 and 1 are not primes
prime[0] = prime[1] = 0;
// Mark composite numbers as false
// and prime numbers as true
for (int i = 2; i * i <= MAX; i++) {
if (prime[i] == 1) {
for (int j = i * i; j <= MAX; j += i) {
prime[j] = 0;
}
}
}
// Update prime[] such that
// prime[i] will store the count of
// all the prime numbers <= i
for (int i = 1; i <= MAX; i++) {
prime[i] += prime[i - 1];
}
}
// Function to return the absolute difference
// between the number of primes and the number
// of composite numbers in the range [l, r]
int getDifference(int l, int r)
{
// Total elements in the range
int total = r - l + 1;
// Count of primes in the range [l, r]
int primes = prime[r] - prime[l - 1];
// Count of composite numbers
// in the range [l, r]
int composites = total - primes;
// Return the sbsolute difference
return (abs(primes - composites));
}
// Driver code
int main()
{
int queries[][2] = { { 1, 10 }, { 5, 30 } };
int q = sizeof(queries) / sizeof(queries[0]);
updatePrimes();
// Perform queries
for (int i = 0; i < q; i++)
cout << getDifference(queries[i][0],
queries[i][1])
<< endl;
return 0;
}
Java
// Java implementation of the approach
import java.io.*;
class GFG
{
static int MAX = 1000000;
static int []prime = new int[MAX + 1];
// Function to update prime[]
// such prime[i] stores the
// count of prime numbers <= i
static void updatePrimes()
{
// prime[] marks all prime numbers as true
// so prime[i] = 1 if ith number is a prime
// Initialization
for (int i = 2; i <= MAX; i++)
{
prime[i] = 1;
}
// 0 and 1 are not primes
prime[0] = prime[1] = 0;
// Mark composite numbers as false
// and prime numbers as true
for (int i = 2; i * i <= MAX; i++)
{
if (prime[i] == 1)
{
for (int j = i * i; j <= MAX; j += i)
{
prime[j] = 0;
}
}
}
// Update prime[] such that
// prime[i] will store the count of
// all the prime numbers <= i
for (int i = 1; i <= MAX; i++)
{
prime[i] += prime[i - 1];
}
}
// Function to return the absolute difference
// between the number of primes and the number
// of composite numbers in the range [l, r]
static int getDifference(int l, int r)
{
// Total elements in the range
int total = r - l + 1;
// Count of primes in the range [l, r]
int primes = prime[r] - prime[l - 1];
// Count of composite numbers
// in the range [l, r]
int composites = total - primes;
// Return the sbsolute difference
return (Math.abs(primes - composites));
}
// Driver code
public static void main (String[] args)
{
int queries[][] = { { 1, 10 }, { 5, 30 } };
int q = queries.length;
updatePrimes();
// Perform queries
for (int i = 0; i < q; i++)
System.out.println (getDifference(queries[i][0],
queries[i][1]));
}
}
// This code is contributed by jit_t
Python3
# Python3 implementation of the approach from math import sqrt MAX = 1000000 prime = [0]*(MAX + 1); # Function to update prime[] # such prime[i] stores the # count of prime numbers <= i def updatePrimes() : # prime[] marks all prime numbers as true # so prime[i] = 1 if ith number is a prime # Initialization for i in range(2, MAX + 1) : prime[i] = 1; # 0 and 1 are not primes prime[0] = prime[1] = 0; # Mark composite numbers as false # and prime numbers as true for i in range(2, int(sqrt(MAX) + 1)) : if (prime[i] == 1) : for j in range(i*i, MAX, i) : prime[j] = 0; # Update prime[] such that # prime[i] will store the count of # all the prime numbers <= i for i in range(1, MAX) : prime[i] += prime[i - 1]; # Function to return the absolute difference # between the number of primes and the number # of composite numbers in the range [l, r] def getDifference(l, r) : # Total elements in the range total = r - l + 1; # Count of primes in the range [l, r] primes = prime[r] - prime[l - 1]; # Count of composite numbers # in the range [l, r] composites = total - primes; # Return the sbsolute difference return (abs(primes - composites)); # Driver code if __name__ == "__main__" : queries = [ [ 1, 10 ],[ 5, 30 ] ]; q = len(queries); updatePrimes(); # Perform queries for i in range(q) : print(getDifference(queries[i][0], queries[i][1])) # This code is contributed by AnkitRai01
C#
// C# implementation of the approach
using System;
class GFG
{
static int MAX = 1000000;
static int []prime = new int[MAX + 1];
// Function to update prime[]
// such prime[i] stores the
// count of prime numbers <= i
static void updatePrimes()
{
// prime[] marks all prime numbers as true
// so prime[i] = 1 if ith number is a prime
// Initialization
for (int i = 2; i <= MAX; i++)
{
prime[i] = 1;
}
// 0 and 1 are not primes
prime[0] = prime[1] = 0;
// Mark composite numbers as false
// and prime numbers as true
for (int i = 2; i * i <= MAX; i++)
{
if (prime[i] == 1)
{
for (int j = i * i; j <= MAX; j += i)
{
prime[j] = 0;
}
}
}
// Update prime[] such that
// prime[i] will store the count of
// all the prime numbers <= i
for (int i = 1; i <= MAX; i++)
{
prime[i] += prime[i - 1];
}
}
// Function to return the absolute difference
// between the number of primes and the number
// of composite numbers in the range [l, r]
static int getDifference(int l, int r)
{
// Total elements in the range
int total = r - l + 1;
// Count of primes in the range [l, r]
int primes = prime[r] - prime[l - 1];
// Count of composite numbers
// in the range [l, r]
int composites = total - primes;
// Return the sbsolute difference
return (Math.Abs(primes - composites));
}
// Driver code
public static void Main ()
{
int [,]queries = { { 1, 10 }, { 5, 30 } };
int q = queries.GetLength(0);
updatePrimes();
// Perform queries
for (int i = 0; i < q; i++)
Console.WriteLine(getDifference(queries[i,0],
queries[i,1]));
}
}
/* This code contributed by PrinciRaj1992 */
Javascript
<script>
// Javascript implementation of the approach
const MAX = 1000000;
let prime = new Array(MAX + 1);
// Function to update prime[]
// such prime[i] stores the
// count of prime numbers <= i
function updatePrimes()
{
// prime[] marks all prime numbers as true
// so prime[i] = 1 if ith number is a prime
// Initialization
for (let i = 2; i <= MAX; i++) {
prime[i] = 1;
}
// 0 and 1 are not primes
prime[0] = prime[1] = 0;
// Mark composite numbers as false
// and prime numbers as true
for (let i = 2; i * i <= MAX; i++) {
if (prime[i] == 1) {
for (let j = i * i; j <= MAX; j += i)
{
prime[j] = 0;
}
}
}
// Update prime[] such that
// prime[i] will store the count of
// all the prime numbers <= i
for (let i = 1; i <= MAX; i++) {
prime[i] += prime[i - 1];
}
}
// Function to return the absolute difference
// between the number of primes and the number
// of composite numbers in the range [l, r]
function getDifference(l, r)
{
// Total elements in the range
let total = r - l + 1;
// Count of primes in the range [l, r]
let primes = prime[r] - prime[l - 1];
// Count of composite numbers
// in the range [l, r]
let composites = total - primes;
// Return the sbsolute difference
return (Math.abs(primes - composites));
}
// Driver code
let queries = [ [ 1, 10 ], [ 5, 30 ] ];
let q = queries.length;
updatePrimes();
// Perform queries
for (let i = 0; i < q; i++)
document.write(getDifference(queries[i][0],
queries[i][1]) + "<br>");
</script>
Producción:
2 10
Espacio Auxiliar: O(1000000)