Dada una array 2D Q[][] de tamaño N * 2 que representa consultas de la forma {L, R} . Para cada consulta, la tarea es imprimir el conteo de números en el rango [L, R] con un conteo de factores primos igual a un número primo .
Ejemplos:
Entrada: Q[][] = {{4, 8}, {30, 32}}
Salida: 3 2
Explicación:
Consulta 1:
Factores primos de 4 = {2, 2} y recuento de factores primos = 2
Factores primos de 5 = {5} y recuento de factores primos = 1
Factores primos de 6 = {2, 3} y recuento de factores primos = 2
Factores primos de 7 = {7} y recuento de factores primos = 1
Factores primos de 8 = { 2, 2, 2} y conteo de factores primos = 3
Por lo tanto, el conteo total de números en el rango [4, 8] que tiene el conteo de factores primos es un número primo es 3.
Consulta 2:
Factores primos de 30 = {2 , 3, 5} y número de factores primos = 3
Factores primos de 31 = {31} y número de factores primos = 1
Factores primos de 32 = {2, 2, 2, 2, 2} y conteo de factores primos = 5
Por lo tanto, el conteo total de números en el rango [4, 8] que tiene el conteo de factores primos es un número primo es 2.Entrada: Q[][] = {{7, 12}, {10, 99}}
Salida: 4
Enfoque ingenuo: el enfoque más simple para resolver este problema es atravesar todos los números en el rango [L, R] y, para cada número, verificar si el conteo de factores primos del número es un número primo o no. Si se determina que es cierto, incremente el contador en 1 . Después de atravesar, imprima el valor del contador para cada consulta.
Complejidad de tiempo: O(|Q| * (max(arr[i][1] – arr[i][0] + 1)) * sqrt(max(arr[i][1]))
Espacio auxiliar: O ( 1)
Enfoque eficiente: para optimizar el enfoque anterior, la idea es precalcular el factor primo más pequeño de cada número en el rango [L i , R i ] usando la criba de Eratóstenes . Siga los pasos a continuación para resolver el problema:
- Genere y almacene el factor primo más pequeño de cada elemento usando la Tamiz de Eratóstenes .
- Encuentre el conteo de factores primos para cada número en el rango [L i , R i ] usando el Sieve .
- Para cada número, comprueba si el recuento total de factores primos es un número primo o no. Si se encuentra que es cierto, entonces incremente el contador.
- Cree una array de suma de prefijos, digamos sum[], donde sum[i] almacenará la suma de los elementos del rango [0, i] cuyo recuento de factores primos es un número primo.
- Finalmente, para cada consulta, imprima el valor sum[arr[i][1]] – sum[arr[i][0] – 1] .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to implement
// the above approach
#include <bits/stdc++.h>
using namespace std;
#define MAX 1001
// Function to find the smallest prime factor
// of all the numbers in range [0, MAX]
vector<int> sieve()
{
// Stores smallest prime factor of all
// the numbers in the range [0, MAX]
vector<int> spf(MAX);
// No smallest prime factor of
// 0 and 1 exists
spf[0] = spf[1] = -1;
// Traverse all the numbers
// in the range [1, MAX]
for (int i = 2; i < MAX; i++) {
// Update spf[i]
spf[i] = i;
}
// Update all the numbers whose
// smallest prime factor is 2
for (int i = 4; i < MAX; i = i + 2) {
spf[i] = 2;
}
// Traverse all the numbers in
// the range [1, sqrt(MAX)]
for (int i = 3; i * i < MAX; i++) {
// Check if i is a prime number
if (spf[i] == i) {
// Update all the numbers whose
// smallest prime factor is i
for (int j = i * i; j < MAX;
j = j + i) {
// Check if j is
// a prime number
if (spf[j] == j) {
spf[j] = i;
}
}
}
}
return spf;
}
// Function to find count of
// prime factor of num
int countFactors(vector<int>& spf, int num)
{
// Stores count of
// prime factor of num
int count = 0;
// Calculate count of
// prime factor
while (num > 1) {
// Update count
count++;
// Update num
num = num / spf[num];
}
return count;
}
// Function to precalculate the count of
// numbers in the range [0, i] whose count
// of prime factors is a prime number
vector<int> precalculateSum(vector<int>& spf)
{
// Stores the sum of all the numbers
// in the range[0, i] count of
// prime factor is a prime number
vector<int> sum(MAX);
// Update sum[0]
sum[0] = 0;
// Traverse all the numbers in
// the range [1, MAX]
for (int i = 1; i < MAX; i++) {
// Stores count of prime factor of i
int prime_factor
= countFactors(spf, i);
// If count of prime factor is
// a prime number
if (spf[prime_factor] == prime_factor) {
// Update sum[i]
sum[i] = sum[i - 1] + 1;
}
else {
// Update sum[i]
sum[i] = sum[i - 1];
}
}
return sum;
}
// Driver Code
int main()
{
// Stores smallest prime factor of all
// the numbers in the range [0, MAX]
vector<int> spf = sieve();
// Stores the sum of all the numbers
// in the range[0, i] count of
// prime factor is a prime number
vector<int> sum = precalculateSum(spf);
int Q[][2] = { { 4, 8 }, { 30, 32 } };
// int N = sizeof(Q) / sizeof(Q[0]);
for (int i = 0; i < 2; i++) {
cout << (sum[Q[i][1]] - sum[Q[i][0] - 1])
<< " ";
}
return 0;
}
Java
// Java program to implement
// the above approach
import java.util.*;
class GFG{
public static int MAX = 1001;
// Function to find the smallest prime factor
// of all the numbers in range [0, MAX]
public static int[] sieve()
{
// Stores smallest prime factor of all
// the numbers in the range [0, MAX]
int spf[] = new int[MAX];
// No smallest prime factor of
// 0 and 1 exists
spf[0] = spf[1] = -1;
// Traverse all the numbers
// in the range [1, MAX]
for(int i = 2; i < MAX; i++)
{
// Update spf[i]
spf[i] = i;
}
// Update all the numbers whose
// smallest prime factor is 2
for(int i = 4; i < MAX; i = i + 2)
{
spf[i] = 2;
}
// Traverse all the numbers in
// the range [1, sqrt(MAX)]
for(int i = 3; i * i < MAX; i++)
{
// Check if i is a prime number
if (spf[i] == i)
{
// Update all the numbers whose
// smallest prime factor is i
for(int j = i * i; j < MAX; j = j + i)
{
// Check if j is
// a prime number
if (spf[j] == j)
{
spf[j] = i;
}
}
}
}
return spf;
}
// Function to find count of
// prime factor of num
public static int countFactors(int spf[], int num)
{
// Stores count of
// prime factor of num
int count = 0;
// Calculate count of
// prime factor
while (num > 1)
{
// Update count
count++;
// Update num
num = num / spf[num];
}
return count;
}
// Function to precalculate the count of
// numbers in the range [0, i] whose count
// of prime factors is a prime number
public static int[] precalculateSum(int spf[])
{
// Stores the sum of all the numbers
// in the range[0, i] count of
// prime factor is a prime number
int sum[] = new int[MAX];
// Update sum[0]
sum[0] = 0;
// Traverse all the numbers in
// the range [1, MAX]
for(int i = 1; i < MAX; i++)
{
// Stores count of prime factor of i
int prime_factor = countFactors(spf, i);
// If count of prime factor is
// a prime number
if (spf[prime_factor] == prime_factor)
{
// Update sum[i]
sum[i] = sum[i - 1] + 1;
}
else
{
// Update sum[i]
sum[i] = sum[i - 1];
}
}
return sum;
}
// Driver code
public static void main(String[] args)
{
// Stores smallest prime factor of all
// the numbers in the range [0, MAX]
int spf[] = sieve();
// Stores the sum of all the numbers
// in the range[0, i] count of
// prime factor is a prime number
int sum[] = precalculateSum(spf);
int Q[][] = { { 4, 8 }, { 30, 32 } };
// int N = sizeof(Q) / sizeof(Q[0]);
for(int i = 0; i < 2; i++)
{
System.out.print((sum[Q[i][1]] -
sum[Q[i][0] - 1]) + " ");
}
}
}
// This code is contributed by divyeshrabadiya07
Python3
# Python3 program to implement # the above approach MAX = 1001 # Function to find the smallest # prime factor of all the numbers # in range [0, MAX] def sieve(): # Stores smallest prime factor of all # the numbers in the range [0, MAX] global MAX spf = [0] * MAX # No smallest prime factor of # 0 and 1 exists spf[0] = spf[1] = -1 # Traverse all the numbers # in the range [1, MAX] for i in range(2, MAX): # Update spf[i] spf[i] = i # Update all the numbers whose # smallest prime factor is 2 for i in range(4, MAX, 2): spf[i] = 2 # Traverse all the numbers in # the range [1, sqrt(MAX)] for i in range(3, MAX): # Check if i is a prime number if (spf[i] == i): # Update all the numbers whose # smallest prime factor is i for j in range(i * i, MAX): # Check if j is # a prime number if (spf[j] == j): spf[j] = i return spf # Function to find count of # prime factor of num def countFactors(spf, num): # Stores count of # prime factor of num count = 0 # Calculate count of # prime factor while (num > 1): # Update count count += 1 # Update num num = num // spf[num] return count # Function to precalculate the count of # numbers in the range [0, i] whose count # of prime factors is a prime number def precalculateSum(spf): # Stores the sum of all the numbers # in the range[0, i] count of # prime factor is a prime number sum = [0] * MAX # Traverse all the numbers in # the range [1, MAX] for i in range(1, MAX): # Stores count of prime factor of i prime_factor = countFactors(spf, i) # If count of prime factor is # a prime number if (spf[prime_factor] == prime_factor): # Update sum[i] sum[i] = sum[i - 1] + 1 else: # Update sum[i] sum[i] = sum[i - 1] return sum # Driver code if __name__ == '__main__': # Stores smallest prime factor of all # the numbers in the range [0, MAX] spf = sieve() # Stores the sum of all the numbers # in the range[0, i] count of # prime factor is a prime number sum = precalculateSum(spf) Q = [ [ 4, 8 ], [ 30, 32 ] ] sum[Q[0][1]] += 1 # N = sizeof(Q) / sizeof(Q[0]); for i in range(0, 2): print((sum[Q[i][1]] - sum[Q[i][0]]), end = " ") # This code is contributed by Princi Singh
C#
// C# program to implement
// the above approach
using System;
class GFG{
public static int MAX = 1001;
// Function to find the smallest
// prime factor of all the numbers
// in range [0, MAX]
public static int[] sieve()
{
// Stores smallest prime factor
// of all the numbers in the
// range [0, MAX]
int []spf = new int[MAX];
// No smallest prime factor
// of 0 and 1 exists
spf[0] = spf[1] = -1;
// Traverse all the numbers
// in the range [1, MAX]
for(int i = 2; i < MAX; i++)
{
// Update spf[i]
spf[i] = i;
}
// Update all the numbers whose
// smallest prime factor is 2
for(int i = 4; i < MAX; i = i + 2)
{
spf[i] = 2;
}
// Traverse all the numbers in
// the range [1, sqrt(MAX)]
for(int i = 3; i * i < MAX; i++)
{
// Check if i is a prime number
if (spf[i] == i)
{
// Update all the numbers
// whose smallest prime
// factor is i
for(int j = i * i;
j < MAX; j = j + i)
{
// Check if j is
// a prime number
if (spf[j] == j)
{
spf[j] = i;
}
}
}
}
return spf;
}
// Function to find count of
// prime factor of num
public static int countFactors(int []spf,
int num)
{
// Stores count of
// prime factor of num
int count = 0;
// Calculate count of
// prime factor
while (num > 1)
{
// Update count
count++;
// Update num
num = num / spf[num];
}
return count;
}
// Function to precalculate the count of
// numbers in the range [0, i] whose count
// of prime factors is a prime number
public static int[] precalculateSum(int []spf)
{
// Stores the sum of all the numbers
// in the range[0, i] count of
// prime factor is a prime number
int []sum = new int[MAX];
// Update sum[0]
sum[0] = 0;
// Traverse all the numbers in
// the range [1, MAX]
for(int i = 1; i < MAX; i++)
{
// Stores count of prime factor of i
int prime_factor = countFactors(spf, i);
// If count of prime factor is
// a prime number
if (spf[prime_factor] == prime_factor)
{
// Update sum[i]
sum[i] = sum[i - 1] + 1;
}
else
{
// Update sum[i]
sum[i] = sum[i - 1];
}
}
return sum;
}
// Driver code
public static void Main(String[] args)
{
// Stores smallest prime factor
// of all the numbers in the
// range [0, MAX]
int []spf = sieve();
// Stores the sum of all the
// numbers in the range[0, i]
// count of prime factor is a
// prime number
int []sum = precalculateSum(spf);
int [,]Q = {{4, 8}, {30, 32}};
// int N = sizeof(Q) / sizeof(Q[0]);
for(int i = 0; i < 2; i++)
{
Console.Write((sum[Q[i, 1]] -
sum[Q[i, 0] - 1]) +
" ");
}
}
}
// This code is contributed by shikhasingrajput
Javascript
<script>
// Javascript program to implement
// the above approach
let MAX = 1001
// Function to find the smallest prime factor
// of all the numbers in range [0, MAX]
function sieve()
{
// Stores smallest prime factor of all
// the numbers in the range [0, MAX]
let spf = new Array(MAX);
// No smallest prime factor of
// 0 and 1 exists
spf[0] = spf[1] = -1;
// Traverse all the numbers
// in the range [1, MAX]
for (let i = 2; i < MAX; i++) {
// Update spf[i]
spf[i] = i;
}
// Update all the numbers whose
// smallest prime factor is 2
for (let i = 4; i < MAX; i = i + 2) {
spf[i] = 2;
}
// Traverse all the numbers in
// the range [1, sqrt(MAX)]
for (let i = 3; i * i < MAX; i++) {
// Check if i is a prime number
if (spf[i] == i) {
// Update all the numbers whose
// smallest prime factor is i
for (let j = i * i; j < MAX;
j = j + i) {
// Check if j is
// a prime number
if (spf[j] == j) {
spf[j] = i;
}
}
}
}
return spf;
}
// Function to find count of
// prime factor of num
function countFactors(spf, num)
{
// Stores count of
// prime factor of num
let count = 0;
// Calculate count of
// prime factor
while (num > 1) {
// Update count
count++;
// Update num
num = num / spf[num];
}
return count;
}
// Function to precalculate the count of
// numbers in the range [0, i] whose count
// of prime factors is a prime number
function precalculateSum(spf)
{
// Stores the sum of all the numbers
// in the range[0, i] count of
// prime factor is a prime number
let sum = new Array(MAX);
// Update sum[0]
sum[0] = 0;
// Traverse all the numbers in
// the range [1, MAX]
for (let i = 1; i < MAX; i++) {
// Stores count of prime factor of i
let prime_factor
= countFactors(spf, i);
// If count of prime factor is
// a prime number
if (spf[prime_factor] == prime_factor) {
// Update sum[i]
sum[i] = sum[i - 1] + 1;
}
else {
// Update sum[i]
sum[i] = sum[i - 1];
}
}
return sum;
}
// Driver Code
// Stores smallest prime factor of all
// the numbers in the range [0, MAX]
let spf = sieve();
// Stores the sum of all the numbers
// in the range[0, i] count of
// prime factor is a prime number
let sum = precalculateSum(spf);
let Q = [ [ 4, 8 ], [ 30, 32 ] ];
// let N = sizeof(Q) / sizeof(Q[0]);
for (let i = 0; i < 2; i++) {
document.write((sum[Q[i][1]] - sum[Q[i][0] - 1]) +
" ");
}
// This code is contributed by gfgking
</script>
Producción:
3 2
Complejidad de tiempo: O(|Q| + (MAX *log(log(MAX))))
Espacio auxiliar: O(MAX)
Publicación traducida automáticamente
Artículo escrito por akhilsaini y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA