Given a range [l, r], the task is to find the sum of all the even factors of the numbers from the given range.
Examples:
Input: l = 6, r = 8
Output: 22
factors(6) = 1, 2, 3, 6, evenfactors(6) = 2, 6 sumEvenFactors(6) = 2 + 6 = 8
factors(7) = 1, 7, No even factors
factors(8) = 1, 2, 4, 8, evenfactors(8) = 2, 4, 8 sumEvenFactors(8) = 2 + 4 + 8 = 14
Therefore sum of all even factors = 8 + 14 = 22
Input: l = 1, r = 10
Output: 42
Approach: We can modify Sieve Of Eratosthenes to store the sum of all even factors of a number at it’s corresponding index. Then we will make a prefix array to store sum upto that index. And now each query can be answered in O(1) using prefix[r] – prefix[l – 1].
Below is the implementation of the above approach:
C++
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
const int MAX = 100000;
ll prefix[MAX];
void sieve_modified()
{
for ( int i = 2; i < MAX; i += 2) {
for ( int j = i; j < MAX; j += i)
prefix[j] += i;
}
for ( int i = 1; i < MAX; i++)
prefix[i] += prefix[i - 1];
}
ll sumEvenFactors( int L, int R)
{
return (prefix[R] - prefix[L - 1]);
}
int main()
{
sieve_modified();
int l = 6, r = 10;
cout << sumEvenFactors(l, r);
return 0;
}
|
Java
class GFG {
static final int MAX = 100000 ;
static long prefix[] = new long [MAX];
static void sieve_modified()
{
for ( int i = 2 ; i < MAX; i += 2 ) {
for ( int j = i; j < MAX; j += i)
prefix[j] += i;
}
for ( int i = 1 ; i < MAX; i++)
prefix[i] += prefix[i - 1 ];
}
static long sumEvenFactors( int L, int R)
{
return (prefix[R] - prefix[L - 1 ]);
}
public static void main(String args[])
{
sieve_modified();
int l = 6 , r = 10 ;
System.out.print(sumEvenFactors(l, r));
}
}
|
Python3
def sieve_modified():
for i in range ( 2 , MAX , 2 ):
for j in range (i, MAX , i):
prefix[j] + = i
for i in range ( 1 , MAX ):
prefix[i] + = prefix[i - 1 ]
def sumEvenFactors(L, R):
return (prefix[R] - prefix[L - 1 ])
if __name__ = = "__main__" :
MAX = 100000
prefix = [ 0 ] * MAX
sieve_modified()
l, r = 6 , 10
print (sumEvenFactors(l, r))
|
C#
using System;
using System;
class GFG
{
public const int MAX = 100000;
public static long [] prefix = new long [MAX];
public static void sieve_modified()
{
for ( int i = 2; i < MAX; i += 2)
{
for ( int j = i; j < MAX; j += i)
{
prefix[j] += i;
}
}
for ( int i = 1; i < MAX; i++)
{
prefix[i] += prefix[i - 1];
}
}
public static long sumEvenFactors( int L, int R)
{
return (prefix[R] - prefix[L - 1]);
}
public static void Main( string [] args)
{
sieve_modified();
int l = 6, r = 10;
Console.Write(sumEvenFactors(l, r));
}
}
|
Javascript
<script>
var MAX = 100000;
prefix = Array(MAX).fill(0);
function sieve_modified()
{
for ( var i = 2; i < MAX; i += 2) {
for ( var j = i; j < MAX; j += i)
prefix[j] += i;
}
for ( var i = 1; i < MAX; i++)
prefix[i] += prefix[i - 1];
}
function sumEvenFactors(L, R)
{
return (prefix[R] - prefix[L - 1]);
}
sieve_modified();
var l = 6, r = 10;
document.write(sumEvenFactors(l, r));
</script>
|
PHP
<?php
$MAX = 10000;
$prefix = array_fill (0, $MAX , 0);
function sieve_modified()
{
global $MAX , $prefix ;
for ( $i = 2; $i < $MAX ; $i += 2)
{
for ( $j = $i ; $j < $MAX ; $j += $i )
$prefix [ $j ] += $i ;
}
for ( $i = 1; $i < $MAX ; $i ++)
$prefix [ $i ] += $prefix [ $i - 1];
}
function sumEvenFactors( $L , $R )
{
global $MAX , $prefix ;
return ( $prefix [ $R ] - $prefix [ $L - 1]);
}
sieve_modified();
$l = 6;
$r = 10;
echo sumEvenFactors( $l , $r );
?>
|
Approach#2: Using math
Define a function that takes two inputs l and r, the range of numbers Create an empty list to store the even factors of each number Iterate through the range of numbers from l to r (inclusive) For each number, find its factors by iterating from 1 to the square root of the number (inclusive) For each factor, check if it is even If the factor is even, append it to the list of even factors After iterating through all factors, sum up the even factors and return the total sum as output
Algorithm
1. Define a function, sum_even_factors, that takes two integer inputs, l and r
2. Create an empty list, even_factors
3. For i in range l to r (inclusive)
a. Create an empty list, factors
b. For j in range 1 to square root of i+1 (inclusive)
i. If i % j == 0, append j to the list factors, and if i//j is not equal to j, append i//j to the list factors
c. For factor in factors:
i. If factor % 2 == 0, append factor to the list even_factors
4. Return the sum of the elements in the list even_factors as output
C++
#include <iostream>
#include <cmath>
#include <vector>
int sumEvenFactors( int l, int r) {
std::vector< int > evenFactors;
for ( int i = l; i <= r; ++i) {
std::vector< int > factors;
for ( int j = 1; j <= std:: sqrt (i); ++j) {
if (i % j == 0) {
factors.push_back(j);
if (i / j != j) {
factors.push_back(i / j);
}
}
}
for ( int factor : factors) {
if (factor % 2 == 0) {
evenFactors.push_back(factor);
}
}
}
int sum = 0;
for ( int factor : evenFactors) {
sum += factor;
}
return sum;
}
int main() {
int l = 6;
int r = 10;
std::cout << sumEvenFactors(l, r) << std::endl;
return 0;
}
|
Java
import java.util.ArrayList;
public class GFG {
public static int sumEvenFactors( int l, int r)
{
ArrayList<Integer> evenFactors = new ArrayList<>();
for ( int i = l; i <= r; ++i) {
ArrayList<Integer> factors = new ArrayList<>();
for ( int j = 1 ; j <= Math.sqrt(i); ++j) {
if (i % j == 0 ) {
factors.add(j);
if (i / j != j) {
factors.add(i / j);
}
}
}
for ( int factor : factors) {
if (factor % 2 == 0 ) {
evenFactors.add(factor);
}
}
}
int sum = 0 ;
for ( int factor : evenFactors) {
sum += factor;
}
return sum;
}
public static void main(String[] args)
{
int l = 6 ;
int r = 10 ;
System.out.println(sumEvenFactors(l, r));
}
}
|
Python3
import math
def sum_even_factors(l, r):
even_factors = []
for i in range (l, r + 1 ):
factors = []
for j in range ( 1 , int (math.sqrt(i)) + 1 ):
if i % j = = 0 :
factors.append(j)
if i / / j ! = j:
factors.append(i / / j)
for factor in factors:
if factor % 2 = = 0 :
even_factors.append(factor)
return sum (even_factors)
l, r = 6 , 10
print (sum_even_factors(l, r))
|
C#
using System;
using System.Collections.Generic;
public class GFG {
public static int SumEvenFactors( int l, int r)
{
List< int > evenFactors = new List< int >();
for ( int i = l; i <= r; ++i) {
List< int > factors = new List< int >();
for ( int j = 1; j <= Math.Sqrt(i); ++j) {
if (i % j == 0) {
factors.Add(j);
if (i / j != j) {
factors.Add(i / j);
}
}
}
foreach ( int factor in factors)
{
if (factor % 2 == 0) {
evenFactors.Add(factor);
}
}
}
int sum = 0;
foreach ( int factor in evenFactors)
{
sum += factor;
}
return sum;
}
public static void Main()
{
int l = 6;
int r = 10;
Console.WriteLine(SumEvenFactors(l, r));
}
}
|
Javascript
function sumEvenFactors(l, r) {
let evenFactors = [];
for (let i = l; i <= r; i++) {
let factors = [];
for (let j = 1; j <= Math.sqrt(i); j++) {
if (i % j == 0) {
factors.push(j);
if (i / j != j) {
factors.push(i / j);
}
}
}
for (let factor of factors) {
if (factor % 2 == 0) {
evenFactors.push(factor);
}
}
}
return evenFactors.reduce((acc, val) => acc + val, 0);
}
let l = 6;
let r = 10;
console.log(sumEvenFactors(l, r));
|
Time complexity: O(n * sqrt(n)),where n represents the range of numbers between l and r
Space complexity: O(n), where n represents the range of numbers between l and r
METHOD 3:Using counter method.
The program finds the sum of all even factors of numbers in a given range using a list comprehension to generate the even factors and a Counter object to count their occurrences. The sum is computed by iterating over the factor-count pairs in the Counter object and multiplying the factor by its count.
1.Initialize an empty list to store the even factors of numbers in the range [l, r].
2.Iterate over each number in the range [l, r].
3.For each number, iterate over each factor in the range [2, num+1].
4.Check if the factor divides the number evenly and if it is even.
5.If both conditions are satisfied, add the factor to the list of even factors.
6.Create a Counter object from the list of even factors to count the number of occurrences of each factor.
7.Iterate over each factor-count pair in the Counter object and multiply the factor by its count.
8.Add up the products computed in step 7 to obtain the total sum of all even factors.
C++
#include <bits/stdc++.h>
using namespace std;
unordered_map< int , int > getFactorCounts( int l, int r)
{
unordered_map< int , int > factorCounts;
for ( int num = l; num <= r; ++num) {
for ( int factor = 2; factor <= num; ++factor) {
if (num % factor == 0 && factor % 2 == 0) {
factorCounts[factor]++;
}
}
}
return factorCounts;
}
int sumEvenFactorsCounter( int l, int r)
{
unordered_map< int , int > factorCounts
= getFactorCounts(l, r);
int totalSum = 0;
for ( const auto & entry : factorCounts) {
totalSum += entry.first * entry.second;
}
return totalSum;
}
int main()
{
int l = 6, r = 10;
int result = sumEvenFactorsCounter(l, r);
cout << result << endl;
return 0;
}
|
Java
import java.util.HashMap;
import java.util.Map;
public class GFG {
private static Map<Integer, Integer>
getFactorCounts( int l, int r)
{
Map<Integer, Integer> factorCounts
= new HashMap<>();
for ( int num = l; num <= r; ++num) {
for ( int factor = 2 ; factor <= num; ++factor) {
if (num % factor == 0 && factor % 2 == 0 ) {
factorCounts.put(
factor,
factorCounts.getOrDefault(factor, 0 )
+ 1 );
}
}
}
return factorCounts;
}
private static int sumEvenFactorsCounter( int l, int r)
{
Map<Integer, Integer> factorCounts
= getFactorCounts(l, r);
int totalSum = 0 ;
for (Map.Entry<Integer, Integer> entry :
factorCounts.entrySet()) {
totalSum += entry.getKey() * entry.getValue();
}
return totalSum;
}
public static void main(String[] args)
{
int l = 6 , r = 10 ;
int result = sumEvenFactorsCounter(l, r);
System.out.println(result);
}
}
|
Python3
from collections import Counter
def sum_even_factors_counter(l, r):
factors = [factor for num in range (l, r + 1 ) for factor in range ( 2 , num + 1 ) if num % factor = = 0 and factor % 2 = = 0 ]
factor_counts = Counter(factors)
total_sum = sum ([factor * count for factor, count in factor_counts.items()])
return total_sum
l, r = 6 , 10
result = sum_even_factors_counter(l, r)
print (result)
|
C#
using System;
using System.Collections.Generic;
class Program
{
static Dictionary< int , int > GetFactorCounts( int l, int r)
{
Dictionary< int , int > factorCounts = new Dictionary< int , int >();
for ( int num = l; num <= r; ++num)
{
for ( int factor = 2; factor <= num; ++factor)
{
if (num % factor == 0 && factor % 2 == 0)
{
if (factorCounts.ContainsKey(factor))
factorCounts[factor]++;
else
factorCounts[factor] = 1;
}
}
}
return factorCounts;
}
static int SumEvenFactorsCounter( int l, int r)
{
Dictionary< int , int > factorCounts = GetFactorCounts(l, r);
int totalSum = 0;
foreach ( var entry in factorCounts)
{
totalSum += entry.Key * entry.Value;
}
return totalSum;
}
static void Main()
{
int l = 6, r = 10;
int result = SumEvenFactorsCounter(l, r);
Console.WriteLine(result);
}
}
|
Javascript
function getFactorCounts(l, r) {
let factorCounts = {};
for (let num = l; num <= r; ++num) {
for (let factor = 2; factor <= num; ++factor) {
if (num % factor === 0 && factor % 2 === 0) {
if (factorCounts[factor]) {
factorCounts[factor]++;
} else {
factorCounts[factor] = 1;
}
}
}
}
return factorCounts;
}
function sumEvenFactorsCounter(l, r) {
let factorCounts = getFactorCounts(l, r);
let totalSum = 0;
for (const factor in factorCounts) {
totalSum += factor * factorCounts[factor];
}
return totalSum;
}
let l = 6, r = 10;
let result = sumEvenFactorsCounter(l, r);
console.log(result);
|
Time complexity:
The time complexity of this algorithm is O((r-l+1) * sqrt(r)), where r-l+1 is the size of the input range [l, r], and sqrt(r) is the maximum number of factors that any number in the range [l, r] can have. The inner loop that checks for factors runs from 2 to num+1, which takes O(sqrt(r)) time on average. The outer loop runs r-l+1 times.
Space complexity:
The space complexity of this algorithm is O(sqrt(r)) to store the list of even factors, plus the space required by the Counter object to store the counts of each factor.
Contact Us