Suma de todos los números compuestos que se encuentran en el rango [L, R] para consultas Q

Posted on by Rudeus Greyrat

Dadas las consultas Q en forma de array 2D arr[][] cuyas filas consisten en dos números L y R que denotan el rango [L, R], la tarea es encontrar la suma de todos los números compuestos que se encuentran en el rango [L , R] .
 

Entrada: arr[][] = {{10, 13}, {12, 21}} 
Salida: 
22 
116 
Explicación: 
Del 10 al 13 solo 10 y 12 es el número compuesto. 
Del 12 al 21, hay 7 números compuestos 
12 + 14 + 15 + 16 + 18 + 20 + 21 = 116
Entrada: arr[][] = {{ 10, 10 }, { 258, 785 }, {45, 245 }, { 1, 1000}} 
Salida: 
10 
233196 
23596 
424372 
 

Enfoque: 
La idea es usar la array de suma de prefijos . La suma de todos los números compuestos hasta ese índice en particular se calcula previamente y se almacena en una array pref[] para que cada consulta se pueda responder en tiempo O(1) . 
 

  1. Inicialice la array de prefijos pref[] .
  2. Iterar de 1 a N y verificar si el número es compuesto o no : 
    • Si el número es compuesto entonces, el índice actual de pref[] almacenará la suma del número y el número en el índice anterior de pref[] .
    • De lo contrario, el índice actual de pref[] es el mismo que el valor en el índice anterior de pref[] .
  3. Para consultas Q , la suma de todos los números compuestos para el rango [L, R] se puede encontrar de la siguiente manera: 
     
sum = pref[R] - pref[L - 1]

A continuación se muestra la implementación del enfoque anterior: 
 

C++

// C++ implementation to find the sum
// of all composite numbers
// in the given range
 
#include <bits/stdc++.h>
 
using namespace std;
 
// Prefix array to precompute
// the sum of all composite
// numbers
long long pref[100001];
 
// Function that return number
// num if num is composite
// else return 0
int isComposite(int n)
{
    // Corner cases
    if (n <= 1)
        return 0;
    if (n <= 3)
        return 0;
 
    // This is checked so that we can skip
    // middle five numbers in below loop
    if (n % 2 == 0 || n % 3 == 0)
        return n;
 
    for (int i = 5; i * i <= n; i = i + 6)
        if (n % i == 0 || n % (i + 2) == 0)
            return n;
 
    return 0;
}
 
// Function to precompute the
// sum of all Composite numbers
// upto 10^5
void preCompute()
{
    for (int i = 1; i <= 100000; ++i) {
 
        // isComposite()
        // return the number i
        // if i is Composite
        // else return 0
        pref[i] = pref[i - 1]
                + isComposite(i);
    }
}
 
// Function to print the sum
// for each query
void printSum(int L, int R)
{
    cout << pref[R] - pref[L - 1]
        << endl;
}
 
// Function to print sum of all
// Composite numbers between
// [L, R]
void printSumComposite(int arr[][2],
                    int Q)
{
 
    // Function that pre computes
    // the sum of all Composite
    // numbers
    preCompute();
 
    // Iterate over all Queries
    // to print the sum
    for (int i = 0; i < Q; i++) {
        printSum(arr[i][0], arr[i][1]);
    }
}
 
// Driver code
int main()
{
    // Queries
    int Q = 2;
    int arr[][2] = { { 10, 13 },
                      { 12, 21 } };
 
    // Function that print the
    // the sum of all composite
    // number in Range [L, R]
    printSumComposite(arr, Q);
    return 0;
}

Java

// Java implementation to find the sum
// of all Composite numbers
// in the given range
 
import java.util.*;
 
class GFG {
 
    // Prefix array to precompute
    // the sum of all Composite
    // number
    static int[] pref = new int[100001];
 
    // Function that return number
    // num if num is Composite
    // else return 0
    static int isComposite(int n)
    {
        // Corner cases
        if (n <= 1)
            return 0;
 
        if (n <= 3)
            return 0;
 
        // This is checked so that we can skip
        // middle five numbers in below loop
        if (n % 2 == 0 || n % 3 == 0)
            return n;
 
        for (int i = 5; i * i <= n; i = i + 6)
            if (n % i == 0 || n % (i + 2) == 0)
                return n;
 
        return 0;
    }
 
    // Function to precompute the
    // sum of all Composite numbers
    // upto 100000
    static void preCompute()
    {
        for (int i = 1; i <= 100000; ++i) {
 
            // checkComposite()
            // return the number i
            // if i is Composite
            // else return 0
            pref[i] = pref[i - 1]
                    + isComposite(i);
        }
    }
 
    // Function to print the sum
    // for each query
    static void printSum(int L, int R)
    {
        System.out.print(pref[R] - pref[L - 1]
                        + "\n");
    }
 
    // Function to print sum of all
    // Composite numbers between
    // [L, R]
    static void printSumComposite(int arr[][],
                                int Q)
    {
 
        // Function that pre computes
        // the sum of all Composite
        // numbers
        preCompute();
 
        // Iterate over all Queries
        // to print the sum
        for (int i = 0; i < Q; i++) {
            printSum(arr[i][0], arr[i][1]);
        }
    }
 
    // Driver code
    public static void main(String[] args)
    {
        // Queries
        int Q = 2;
        int arr[][] = { { 10, 13 },
                        { 12, 21 } };
 
        // Function that print the
        // the sum of all Composite
        // number in Range [L, R]
        printSumComposite(arr, Q);
    }
}

Python3

# Python implementation to find the sum
# of all composite numbers
# in the given range
 
# Prefix array to precompute
# the sum of all composite
# number
pref =[0]*100001
 
# Function that return number
# num if num is composite
# else return 0
def isComposite(n):
 
    # Corner cases
    if (n <= 1):
        return 0
    if (n <= 3):
        return 0
 
    # This is checked so that we can skip
    # middle five numbers in below loop
    if (n % 2 == 0 or n % 3 == 0):
        return n
    i = 5
    while(i * i <= n):
         
        if (n % i == 0 or n % (i + 2) == 0):
            return n
        i = i + 6
         
    return 0
 
# Function to precompute the
# sum of all composite numbers
# upto 100000
def preCompute():
    for i in range(1, 100001):
        # checkcomposite()
        # return the number i
        # if i is composite
        # else return 0
        pref[i] = pref[i - 1]+ isComposite(i)
     
 
 
# Function to print the sum
# for each query
def printSum(L, R):
    print(pref[R] - pref[L - 1])
 
 
# Function to print sum of all
# composite numbers between
def printSumcomposite(arr, Q):
     
    # Function that pre computes
    # the sum of all composite
    # numbers
    preCompute()
     
    # Iterate over all Queries
    # to print the sum
    for i in range(Q):
        printSum(arr[i][0], arr[i][1])
     
 
 
# Driver code
if __name__ == "__main__":
    Q = 2
    arr = [[10, 13 ], [ 12, 21 ]]
     
    # Function that print the
    # the sum of all composite
    # number in Range [L, R]
    printSumcomposite(arr, Q)

C#

// C# implementation to find the sum
// of all Composite numbers
// in the given range
using System;
 
public class GFG{
 
// Prefix array to precompute
// the sum of all Composite
// number
static int[] pref = new int[100001];
 
// Function that return number
// num if num is Composite
// else return 0
static int isComposite(int n)
{
 
    // Corner cases
    if (n <= 1)
        return 0;
 
    if (n <= 3)
        return 0;
 
    // This is checked so that we can skip
    // middle five numbers in below loop
    if (n % 2 == 0 || n % 3 == 0)
        return n;
 
    for(int i = 5; i * i <= n; i = i + 6)
       if (n % i == 0 || n % (i + 2) == 0)
           return n;
 
    return 0;
}
 
// Function to precompute the
// sum of all Composite numbers
// upto 100000
static void preCompute()
{
    for(int i = 1; i <= 100000; ++i)
    {
       // CheckComposite()
       // return the number i
       // if i is Composite
       // else return 0
       pref[i] = pref[i - 1] +
                 isComposite(i);
    }
}
 
// Function to print the sum
// for each query
static void printSum(int L, int R)
{
    Console.Write(pref[R] -
                  pref[L - 1] + "\n");
}
 
// Function to print sum of all
// Composite numbers between
// [L, R]
static void printSumComposite(int [,]arr,
                              int Q)
{
 
    // Function that pre computes
    // the sum of all Composite
    // numbers
    preCompute();
 
    // Iterate over all Queries
    // to print the sum
    for(int i = 0; i < Q; i++)
    {
       printSum(arr[i, 0], arr[i, 1]);
    }
}
 
// Driver code
public static void Main(String[] args)
{
 
    // Queries
    int Q = 2;
    int [,]arr = { { 10, 13 },
                   { 12, 21 } };
 
    // Function that print the
    // the sum of all Composite
    // number in Range [L, R]
    printSumComposite(arr, Q);
}
}
 
// This code is contributed by Princi Singh

Javascript

<script>
 
// Javascript implementation to find the sum
// of all composite numbers
// in the given range
 
// Prefix array to precompute
// the sum of all composite
// numbers
var pref = Array(100001).fill(0);
 
// Function that return number
// num if num is composite
// else return 0
function isComposite( n)
{
    // Corner cases
    if (n <= 1)
        return 0;
    if (n <= 3)
        return 0;
 
    // This is checked so that we can skip
    // middle five numbers in below loop
    if (n % 2 == 0 || n % 3 == 0)
        return n;
 
    for (var i = 5; i * i <= n; i = i + 6)
        if (n % i == 0 || n % (i + 2) == 0)
            return n;
 
    return 0;
}
 
// Function to precompute the
// sum of all Composite numbers
// upto 10^5
function preCompute()
{
    for (var i = 1; i <= 100000; ++i) {
 
        // isComposite()
        // return the number i
        // if i is Composite
        // else return 0
        pref[i] = pref[i - 1]
                + isComposite(i);
    }
}
 
// Function to print the sum
// for each query
function printSum(L, R)
{
    document.write( pref[R] - pref[L - 1] +"<br>");
}
 
// Function to print sum of all
// Composite numbers between
// [L, R]
function printSumComposite(arr, Q)
{
 
    // Function that pre computes
    // the sum of all Composite
    // numbers
    preCompute();
 
    // Iterate over all Queries
    // to print the sum
    for (var i = 0; i < Q; i++) {
        printSum(arr[i][0], arr[i][1]);
    }
}
 
// Driver code
// Queries
var Q = 2;
var arr = [ [ 10, 13 ],
                   [ 12, 21 ] ];
// Function that print the
// the sum of all composite
// number in Range [L, R]
printSumComposite(arr, Q);
 
 
</script>
Producción: 

22 
116

 

Complejidad de tiempo: O (MAX 3/2 ), donde MAX = 100000

Espacio Auxiliar: O(1)

Publicación traducida automáticamente

Artículo escrito por spp____ y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *