Sum of all odd factors of numbers in the range [l, r]
Given a range [l, r], the task is to find the sum of all the odd factors of the numbers from the given range.
Examples:
Input: l = 6, r = 8
Output: 32
factors(6) = 1, 2, 3, 6, oddfactors(6) = 1, 3 sum_Odd_Factors(6) = 1 + 3 = 4
factors(7) = 1, 7, oddfactors(6) = 1 7, sum_Odd_Factors(7) = 1 + 7 = 8
factors(8) = 1, 2, 4, 8, oddfactors(6) = 1, sum_Odd_Factors(8) = 1 = 1
Therefore sum of all odd factors = 4 + 8 + 1 = 13
Input: l = 1, r = 10
Output: 45
Approach: We can modify Sieve Of Eratosthenes to store sum of all odd 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++
// 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
// 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
# 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#
// 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 // 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 ?> |
Javascript
<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
Time Complexity: O(MAX log MAX), we are using a nested loop.
Auxiliary Space: O(MAX), we are using pre[Max] extra space.