Suma de todos los factores impares de números en el rango [l, r]

Dado un rango [l, r] , la tarea es encontrar la suma de todos los factores impares de los números del rango dado.
Ejemplos: 
 

Entrada: l = 6, r = 8 
Salida: 32 
factores (6) = 1, 2, 3, 6, factores impares (6) = 1, 3 sum_Odd_Factors (6) = 1 + 3 = 4 
factores (7) = 1, 7, factores impares (6) = 1 7, sum_Odd_Factors (7) = 1 + 7 = 8 
factores (8) = 1, 2, 4, 8, factores impares (6) = 1, sum_Odd_Factors (8) = 1 = 1 
Por lo tanto suma de todos los factores impares = 4 + 8 + 1 = 13
Entrada: l = 1, r = 10 
Salida: 45 
 

Enfoque: podemos modificar la criba de Eratóstenes para almacenar la suma de todos los factores impares de un número en su índice correspondiente. Luego haremos una array de prefijos para almacenar la suma hasta ese índice. Y ahora cada consulta se puede responder en O(1) usando prefijo[r] – prefijo[l – 1].
A continuación se muestra la implementación del enfoque anterior:
 

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
 
const int MAX = 100001;
 
ll prefix[MAX];
 
// Function to calculate the prefix sum
// of all the odd factors
void sieve_modified()
{
    for (int i = 1; i < MAX; i += 2) {
 
        // Add i to all the multiples of i
        for (int j = i; j < MAX; j += i)
            prefix[j] += i;
    }
 
    // Update the prefix sum
    for (int i = 1; i < MAX; i++)
        prefix[i] += prefix[i - 1];
}
 
// Function to return the sum of
// all the odd factors of the
// numbers in the given range
ll sumOddFactors(int L, int R)
{
    return (prefix[R] - prefix[L - 1]);
}
 
// Driver code
int main()
{
    sieve_modified();
    int l = 6, r = 10;
    cout << sumOddFactors(l, r);
    return 0;
}

// Java implementation of the approach
import java.io.*;
 
class GFG
{
     
static int MAX = 100001;
static int prefix[] = new int[MAX];
 
// Function to calculate the prefix sum
// of all the odd factors
static void sieve_modified()
{
    for (int i = 1; i < MAX; i += 2)
    {
 
        // Add i to all the multiples of i
        for (int j = i; j < MAX; j += i)
            prefix[j] += i;
    }
 
    // Update the prefix sum
    for (int i = 1; i < MAX; i++)
        prefix[i] += prefix[i - 1];
}
 
// Function to return the sum of
// all the odd factors of the
// numbers in the given range
static int sumOddFactors(int L, int R)
{
    return (prefix[R] - prefix[L - 1]);
}
 
    // Driver code
    public static void main (String[] args)
    {
        sieve_modified();
        int l = 6, r = 10;
        System.out.println (sumOddFactors(l, r));
    }
}
 
// This code is contributed by jit_t

# Python3 implementation of the approach
MAX = 100001;
 
prefix = [0] * MAX;
 
# Function to calculate the prefix sum
# of all the odd factors
def sieve_modified():
 
    for i in range(1, MAX, 2):
 
        # Add i to all the multiples of i
        for j in range(i, MAX, i):
            prefix[j] += i;
 
    # Update the prefix sum
    for i in range(1, MAX):
        prefix[i] += prefix[i - 1];
 
# Function to return the sum of
# all the odd factors of the
# numbers in the given range
def sumOddFactors(L, R):
 
    return (prefix[R] - prefix[L - 1]);
 
# Driver code
sieve_modified();
l = 6;
r = 10;
print(sumOddFactors(l, r));
 
# this code is contributed by chandan_jnu

// C# implementation of the approach
using System;
 
class GFG
{
 
public static int MAX = 100001;
public static int[] prefix = new int[MAX];
 
// Function to calculate the prefix sum
// of all the odd factors
public static void sieve_modified()
{
    for (int i = 1; i < MAX; i += 2)
    {
 
        // Add i to all the multiples of i
        for (int j = i; j < MAX; j += i)
        {
            prefix[j] += i;
        }
    }
 
    // Update the prefix sum
    for (int i = 1; i < MAX; i++)
    {
        prefix[i] += prefix[i - 1];
    }
}
 
// Function to return the sum of
// all the odd factors of the
// numbers in the given range
public static int sumOddFactors(int L, int R)
{
    return (prefix[R] - prefix[L - 1]);
}
 
// Driver code
public static void Main(string[] args)
{
    sieve_modified();
    int l = 6, r = 10;
    Console.WriteLine(sumOddFactors(l, r));
}
}
 
// This code is contributed by Shrikant13

<?php
// PHP implementation of the approach
 
$MAX = 10001;
 
$prefix = array_fill(0, $MAX, 0);
 
// Function to calculate the prefix
// sum of all the odd factors
function sieve_modified()
{
    global $prefix, $MAX;
    for ($i = 1; $i < $MAX; $i += 2)
    {
 
        // Add i to all the multiples of i
        for ($j = $i; $j < $MAX; $j += $i)
            $prefix[$j] += $i;
    }
 
    // Update the prefix sum
    for ($i = 1; $i < $MAX; $i++)
        $prefix[$i] += $prefix[$i - 1];
}
 
// Function to return the sum of
// all the odd factors of the
// numbers in the given range
function sumOddFactors($L, $R)
{
    global $prefix;
    return ($prefix[$R] -
            $prefix[$L - 1]);
}
 
// Driver code
sieve_modified();
$l = 6;
$r = 10;
echo sumOddFactors($l, $r);
 
// This code is contributed
// by chandan_jnu
?>

<script>
// Javascript implementation of the approach
var MAX = 100001;
prefix = Array(MAX).fill(0)
 
// Function to calculate the prefix sum
// of all the odd factors
function sieve_modified()
{
    for (var i = 1; i < MAX; i += 2) {
 
        // Add i to all the multiples of i
        for (var j = i; j < MAX; j += i)
            prefix[j] += i;
    }
 
    // Update the prefix sum
    for (var i = 1; i < MAX; i++)
        prefix[i] += prefix[i - 1];
}
 
// Function to return the sum of
// all the odd factors of the
// numbers in the given range
function sumOddFactors(L, R)
{
    return (prefix[R] - prefix[L - 1]);
}
 
// Driver code
sieve_modified();
var l = 6, r = 10;
document.write(sumOddFactors(l, r));
 
// This code is contributed by noob2000.
 
</script>

32

Complejidad de tiempo: O (100001 * 100001), estamos usando un bucle anidado.

Espacio auxiliar: O(100001), estamos usando espacio extra pre[Max].