Consultas sobre la suma de recuentos de factores primos en un rango

Hay consultas Q. Cada consulta tiene la forma de L y R . La tarea es generar la suma del número de factores primos de cada número en el rango dado de cada consulta.
Ejemplos: 
 

Input : Q = 2
        L = 6, R = 10
        L = 1, R = 5        
Output : 7 
         4
For query 1,
6 => 2  [Prime factors are 2 and 3]
7 => 1
8 => 1
9 => 1
10 => 2
Sum = 2 + 1 + 1 + 1 + 2 = 7
For query 2,
1 => 0
2 => 1
3 => 1
4 => 1
5 => 1
Sum = 0 + 1 + 1 + 1 + 1 = 4.

Método 1 (fuerza bruta): 
la idea es atravesar de L a R para cada consulta, y para cada número encontrar el número del factor primo y sumarlo a la respuesta.
Método 2 (enfoque eficiente): 
La idea es utilizar el método de la criba de Eratóstenes para contar el número de factores primos de números compuestos. Al igual que el bucle interior de la criba de Eratóstenes se utiliza para marcar el número compuesto. Podemos usarlo para incrementar el factor primo de los números. En lugar de marcar cada celda de la array como 0 o 1, podemos almacenar el número de números primos de ese índice. Y luego, para cada consulta, encuentre la suma de la array de L a R.
A continuación se muestra la implementación de este enfoque: 
 

// C++ program to find sum prime factors
// in given range.
#include <bits/stdc++.h>
#define MAX 1000006
using namespace std;
 
// using sieve method to evaluating
// the prime factor of numbers
void sieve(int count[])
{
    for (int i = 2; i * i <= MAX; i++) {
        // if i is prime
        if (count[i] == 0) {
            for (int j = 2 * i; j < MAX; j += i)
                count[j]++;
 
            // setting number of prime
            // factor of a prime number.
            count[i] = 1;
        }
    }
}
 
// Returns sum of counts of prime factors in
// range from l to r. This function mainly
// uses count[] which is filled by Sieve()
int query(int count[], int l, int r)
{
    int sum = 0;
 
    // finding the sum of number of prime
    // factor of numbers in a range.
    for (int i = l; i <= r; i++)
        sum += count[i];
 
    return sum;
}
 
// Driven Program
int main()
{
    int count[MAX];
    memset(count, 0, sizeof count);
    sieve(count);
 
    cout << query(count, 6, 10) << endl
         << query(count, 1, 5);
 
    return 0;
}

// Java program to find sum prime
// factors in given range.
 
class GFG {
 
    static final int MAX = 1000006;
 
    // using sieve method to evaluating
    // the prime factor of numbers
    static void sieve(int count[])
    {
        for (int i = 2; i * i <= MAX; i++) {
            // if i is prime
            if (count[i] == 0) {
                for (int j = 2 * i; j < MAX; j += i)
                    count[j]++;
 
                // setting number of prime
                // factor of a prime number.
                count[i] = 1;
            }
        }
    }
 
    // Returns sum of counts of prime factors in
    // range from l to r. This function mainly
    // uses count[] which is filled by Sieve()
    static int query(int count[], int l, int r)
    {
        int sum = 0;
 
        // finding the sum of number of prime
        // factor of numbers in a range.
        for (int i = l; i <= r; i++)
            sum += count[i];
 
        return sum;
    }
 
    // Driver code
    public static void main(String[] args)
    {
        int count[] = new int[MAX];
        sieve(count);
 
        System.out.println(query(count, 6, 10) + " " + query(count, 1, 5));
    }
}
 
// This code is contributed by Anant Agarwal.

# Python3 program to find sum prime factors
# in given range.
MAX = 100006;
count = [0] * MAX;
 
# using sieve method to evaluating
# the prime factor of numbers
def sieve():
    i = 2;
    while (i * i <= MAX):
         
        # if i is prime
        if (count[i] == 0):
            for j in range(2 * i, MAX, i):
                count[j] += 1;
             
            # setting number of prime
            # factor of a prime number.
            count[i] = 1;
         
        i += 1;
 
# Returns sum of counts of prime factors in
# range from l to r. This function mainly
# uses count[] which is filled by Sieve()
def query(l, r):
    sum = 0;
 
    # finding the sum of number of prime
    # factor of numbers in a range.
    for i in range(l, r + 1):
        sum += count[i];
 
    return sum;
 
# Driver Code
sieve();
print(query(6, 10), query(1, 5));
 
# This code is contributed by mits

// C# program to find sum prime
// factors in given range.
using System;
 
class GFG {
 
    static int MAX = 1000006;
 
    // using sieve method to evaluating
    // the prime factor of numbers
    static void sieve(int[] count)
    {
        for (int i = 2; i * i <= MAX; i++)
        {
             
            // if i is prime
            if (count[i] == 0) {
                for (int j = 2 * i; j < MAX;
                                     j += i)
                    count[j]++;
 
                // setting number of prime
                // factor of a prime number.
                count[i] = 1;
            }
        }
    }
 
    // Returns sum of counts of prime factors
    // in range from l to r. This function
    // mainly uses count[] which is filled by
    // Sieve()
    static int query(int[] count, int l, int r)
    {
         
        int sum = 0;
 
        // finding the sum of number of prime
        // factor of numbers in a range.
        for (int i = l; i <= r; i++)
            sum += count[i];
 
        return sum;
    }
 
    // Driver code
    public static void Main()
    {
         
        int[] count = new int[MAX];
        sieve(count);
 
        Console.Write(query(count, 6, 10) +
                " " + query(count, 1, 5));
    }
}
 
// This code is contributed by nitin mittal.

<?php
// PHP program to find sum prime factors
// in given range.
$MAX = 100006;
 
// using sieve method to evaluating
// the prime factor of numbers
function sieve(&$count)
{
    global $MAX;
    for ($i = 2; $i * $i <= $MAX; $i++)
    {
        // if i is prime
        if ($count[$i] == 0)
        {
            for ($j = 2 * $i; $j < $MAX; $j += $i)
                $count[$j]++;
 
            // setting number of prime
            // factor of a prime number.
            $count[$i] = 1;
        }
    }
}
 
// Returns sum of counts of prime factors in
// range from l to r. This function mainly
// uses count[] which is filled by Sieve()
function query($count, $l, $r)
{
    $sum = 0;
 
    // finding the sum of number of prime
    // factor of numbers in a range.
    for ($i = $l; $i <= $r; $i++)
        $sum += $count[$i];
 
    return $sum;
}
 
// Driver Code
$count = array_fill(0, $MAX, 0);
sieve($count);
 
echo query($count, 6, 10) . " " .
     query($count, 1, 5);
 
// This code is contributed by mits
?>

<script>
 
// Javascript program to find sum prime
// factors in given range.
var MAX = 1000006;
 
    // using sieve method to evaluating
// the prime factor of numbers
function sieve(count)
{
    for (i = 2; i * i <= MAX; i++) {
        // if i is prime
        if (count[i] == 0) {
            for (j = 2 * i; j < MAX; j += i)
                count[j]++;
 
            // setting number of prime
            // factor of a prime number.
            count[i] = 1;
        }
    }
}
 
// Returns sum of counts of prime factors in
// range from l to r. This function mainly
// uses count which is filled by Sieve()
function query(count , l , r)
{
    var sum = 0;
 
    // finding the sum of number of prime
    // factor of numbers in a range.
    for (i = l; i <= r; i++)
        sum += count[i];
 
    return sum;
}
 
// Driver code
var count = Array.from({length: MAX},
(_, i) => 0);
sieve(count);
 
document.write(query(count, 6, 10) + " " +
query(count, 1, 5));
 
// This code contributed by shikhasingrajput
 
</script>

Producción:  

7 4

Este artículo es una contribución de Anuj chauhan . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a contribuido@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.