Given two integers L and R. The task is to find the sum of all prime factors of every number in the range[L-R].
Examples:
Input: l = 5, r = 10
Output: 17
5 is prime, hence sum of factors = 0
6 has prime factors 2 and 3, hence sum = 5
7 is prime, hence sum = 0
8 has prime factor 2, hence sum = 2
9 has prime factor 3, hence sum = 3
10 has prime factors 2 and 5, hence sum = 7
Hence, total sum = 5 + 2 + 3 + 7 = 17
Input: l = 18, r = 25
Output: 45
18 has prime factors 2, 3 hence sum = 5
19 is prime, hence sum of factors = 0
20 has prime factors 2 and 5, hence sum = 7
21 has prime factors 3 and 7, hence sum = 10
22 has prime factors 2 and 11, hence sum = 13
23 is prime. hence sum = 0
24 has prime factors 2 and 3, hence sum = 5
25 has prime factor 5, hence sum = 5
Hence, total sum = 5 + 7 + 10 + 13 + 5 + 5 = 45
A naive approach would be to start iterating through all numbers from l to r. For each iteration, start from 2 to i and find if i is divisible by that number, if it is divisible, we simply add i and proceed.
Below is the implementation of the above approach.
C++
// C++ program to find the sum of prime // factors of all numbers in range [L-R] #include <iostream>using namespace std; bool isPrime(int n) { for (int i = 2; i * i <= n; i++) { // n has a factor, hence not a prime if (n % i == 0) return false; } // we reach here if n has no factors // and hence n is a prime number return true; } int sum(int l, int r) { int sum = 0; // iterate from lower to upper for (int i = l; i <= r; i++) { // if i is prime, it has no factors if (isPrime(i)) continue; for (int j = 2; j < i; j++) { // check if j is a prime factor of i if (i % j == 0 && isPrime(j)) sum += j; } } return sum; } // Driver codeint main() { int l = 18, r = 25; cout<<(sum(l, r)); return 0;} |
Java
// Java program to find the sum of prime// factors of all numbers in range [L-R]class gfg { static boolean isPrime(int n) { for (int i = 2; i * i <= n; i++) { // n has a factor, hence not a prime if (n % i == 0) return false; } // we reach here if n has no factors // and hence n is a prime number return true; } static int sum(int l, int r) { int sum = 0; // iterate from lower to upper for (int i = l; i <= r; i++) { // if i is prime, it has no factors if (isPrime(i)) continue; for (int j = 2; j < i; j++) { // check if j is a prime factor of i if (i % j == 0 && isPrime(j)) sum += j; } } return sum; } // Driver code public static void main(String[] args) { int l = 18, r = 25; System.out.println(sum(l, r)); }} |
Python3
# Python3 program to find the sum of prime # factors of all numbers in range [L-R] def isPrime(n): i = 2 while i * i <= n: # n has a factor, hence not a prime if (n % i == 0): return False i += 1 # we reach here if n has no factors # and hence n is a prime number return True def sum(l, r): sum = 0 # iterate from lower to upper for i in range(l, r + 1) : # if i is prime, it has no factors if (isPrime(i)) : continue for j in range(2, i): # check if j is a prime factor of i if (i % j == 0 and isPrime(j)) : sum += j return sum # Driver codeif __name__ == "__main__": l = 18 r = 25 print(sum(l, r))# This code is contributed by ita_c |
C#
// C# program to find the sum // of prime factors of all // numbers in range [L-R]using System;class GFG{ static bool isPrime(int n) { for (int i = 2; i * i <= n; i++) { // n has a factor, // hence not a prime if (n % i == 0) return false; } // we reach here if n has // no factors and hence n // is a prime number return true; } static int sum(int l, int r) { int sum = 0; // iterate from lower to upper for (int i = l; i <= r; i++) { // if i is prime, it // has no factors if (isPrime(i)) continue; for (int j = 2; j < i; j++) { // check if j is a // prime factor of i if (i % j == 0 && isPrime(j)) sum += j; } } return sum; } // Driver code public static void Main() { int l = 18, r = 25; Console.WriteLine(sum(l, r)); }}// This code is contributed // by Akanksha Rai(Abby_akku) |
PHP
<?php// PHP program to find the // sum of prime factors of // all numbers in range [L-R]function isPrime($n){ for ($i = 2; $i * $i <= $n; $i++) { // n has a factor, hence // not a prime if ($n % $i == 0) return false; } // we reach here if n has // no factors and hence n // is a prime number return true;}function sum1($l, $r){ $sum = 0; // iterate from lower to upper for ($i = $l; $i <= $r; $i++) { // if i is prime, it // has no factors if (isPrime($i)) continue; for ($j = 2; $j < $i; $j++) { // check if j is a // prime factor of i if ($i % $j == 0 && isPrime($j)) $sum += $j; } } return $sum;}// Driver Code$l = 18;$r = 25;echo sum1($l, $r);// This code is contributed by mits?> |
Javascript
<script>// Javascript program to find the sum of prime// factors of all numbers in range [L-R] function isPrime(n) { for (let i = 2; i * i <= n; i++) { // n has a factor, hence not a prime if (n % i == 0) return false; } // we reach here if n has no factors // and hence n is a prime number return true; } function sum(l,r) { let sum = 0; // iterate from lower to upper for (let i = l; i <= r; i++) { // if i is prime, it has no factors if (isPrime(i)) continue; for (let j = 2; j < i; j++) { // check if j is a prime factor of i if (i % j == 0 && isPrime(j)) sum += j; } } return sum; } // Driver code let l = 18, r = 25; document.write(sum(l, r)); // This code is contributed by rag2127</script> |
Output
45
Time Complexity: O(N * N * sqrt(N))
Auxiliary Space: O(1) as it is using constant space for variables
An efficient approach is to modify the sieve of Eratosthenes slightly to find the sum of all prime divisors. Next, maintain a prefix array to keep the sum of the sum of all prime divisors up to index i. Hence, pref_arr[r] – pref_arr[l-1] would give the answer.
Below is the implementation of the above approach.
C++
// C++ program to find the sum of prime// factors of all numbers in range [L-R]#include<bits/stdc++.h>using namespace std;#define N 10000long arr[N]; // function to compute the sieve void sieve() { for (int i = 2; i * i < N; i++) { // i is prime if (arr[i] == 0) { // add i to all the multiples of i till N for (int j = 2; i * j < N; j++) { arr[i * j] += i; } } } } // function that returns the sum long sum(int l, int r) { // Function call to compute sieve sieve(); // prefix array to keep the // sum of all arr[i] till i long pref_arr[r+1]; pref_arr[0] = arr[0]; // calculate the prefix sum of prime divisors for (int i = 1; i <= r; i++) { pref_arr[i] = pref_arr[i - 1] + arr[i]; } // lower is the beginning of array if (l == 1) return (pref_arr[r]); // lower is not the beginning of the array else return (pref_arr[r] - pref_arr[l - 1]); } // Driver Code int main() { int l = 5, r = 10; cout<<(sum(l, r)); return 0; } // This code is contributed by Rajput-Ji |
Java
// Java program to find the sum of prime// factors of all numbers in range [L-R]public class gfg { static int N = 10000; static long arr[] = new long[N]; // function to compute the sieve static void sieve() { for (int i = 2; i * i < N; i++) { // i is prime if (arr[i] == 0) { // add i to all the multiples of i till N for (int j = 2; i * j < N; j++) { arr[i * j] += i; } } } } // function that returns the sum static long sum(int l, int r) { // Function call to compute sieve sieve(); // prefix array to keep the sum of all arr[i] till i long[] pref_arr = new long[r + 1]; pref_arr[0] = arr[0]; // calculate the prefix sum of prime divisors for (int i = 1; i <= r; i++) { pref_arr[i] = pref_arr[i - 1] + arr[i]; } // lower is the beginning of array if (l == 1) return (pref_arr[r]); // lower is not the beginning of the array else return (pref_arr[r] - pref_arr[l - 1]); } // Driver Code public static void main(String[] args) { int l = 5, r = 10; System.out.println(sum(l, r)); }} |
Python3
# Python3 program to find the sum of prime# factors of all numbers in range [L-R]N = 10000;arr = [0] * N;# function to compute the sievedef sieve(): i = 2; while(i * i < N): # i is prime if (arr[i] == 0): # add i to all the multiple # of i till N j = 2; while (i * j < N): arr[i * j] += i; j += 1; i += 1;# function that returns the sumdef sum(l, r): # Function call to compute sieve sieve(); # prefix array to keep the # sum of all arr[i] till i pref_arr = [0] * (r + 1); pref_arr[0] = arr[0]; # calculate the prefix sum # of prime divisors for i in range(1, r + 1): pref_arr[i] = pref_arr[i - 1] + arr[i]; # lower is the beginning of array if (l == 1): return (pref_arr[r]); # lower is not the beginning # of the array else: return (pref_arr[r] - pref_arr[l - 1]);# Driver Codel = 5;r = 10;print(sum(l, r));# This code is contributed by mits |
C#
// C# program to find the sum // of prime factors of all // numbers in range [L-R]using System;class GFG { static int N = 10000; static long[] arr = new long[N]; // function to compute // the sieve static void sieve() { for (int i = 2; i * i < N; i++) { // i is prime if (arr[i] == 0) { // add i to all the multiples // of i till N for (int j = 2; i * j < N; j++) { arr[i * j] += i; } } } } // function that // returns the sum static long sum(int l, int r) { // Function call to // compute sieve sieve(); // prefix array to keep the // sum of all arr[i] till i long[] pref_arr = new long[r + 1]; pref_arr[0] = arr[0]; // calculate the prefix // sum of prime divisors for (int i = 1; i <= r; i++) { pref_arr[i] = pref_arr[i - 1] + arr[i]; } // lower is the beginning // of array if (l == 1) return (pref_arr[r]); // lower is not the // beginning of the array else return (pref_arr[r] - pref_arr[l - 1]); } // Driver Code public static void Main() { int l = 5, r = 10; Console.WriteLine(sum(l, r)); }}// This code is contributed // by Akanksha Rai(Abby_akku) |
PHP
<?php// PHP program to find the sum of prime// factors of all numbers in range [L-R]$N = 10000;$arr = array_fill(0, $N, 0);// function to compute the sievefunction sieve(){ global $N, $arr; for ($i = 2; $i * $i < $N; $i++) { // i is prime if ($arr[$i] == 0) { // add i to all the multiples // of i till N for ($j = 2; $i * $j < $N; $j++) { $arr[$i * $j] += $i; } } }}// function that returns the sumfunction sum($l, $r){ global $arr; // Function call to compute sieve sieve(); // prefix array to keep the // sum of all arr[i] till i $pref_arr = array_fill(0, $r + 1, 0); $pref_arr[0] = $arr[0]; // calculate the prefix sum // of prime divisors for ($i = 1; $i <= $r; $i++) { $pref_arr[$i] = $pref_arr[$i - 1] + $arr[$i]; } // lower is the beginning of array if ($l == 1) return ($pref_arr[$r]); // lower is not the beginning // of the array else return ($pref_arr[$r] - $pref_arr[$l - 1]);}// Driver Code$l = 5;$r = 10;echo(sum($l, $r));// This code is contributed by mits?> |
Javascript
<script>// Javascript program to find the sum of prime// factors of all numbers in range [L-R] let N = 10000; let arr=new Array(N); for(let i=0;i<N;i++) { arr[i]=0; } // function to compute the sieve function sieve() { for (let i = 2; i * i < N; i++) { // i is prime if (arr[i] == 0) { // add i to all the multiples of i till N for (let j = 2; i * j < N; j++) { arr[i * j] += i; } } } } // function that returns the sum function sum(l,r) { // Function call to compute sieve sieve(); // prefix array to keep the sum of all arr[i] till i let pref_arr = new Array(r + 1); pref_arr[0] = arr[0]; // calculate the prefix sum of prime divisors for (let i = 1; i <= r; i++) { pref_arr[i] = pref_arr[i - 1] + arr[i]; } // lower is the beginning of array if (l == 1) return (pref_arr[r]); // lower is not the beginning of the array else return (pref_arr[r] - pref_arr[l - 1]); } // Driver Code let l = 5, r = 10; document.write(sum(l, r)); // This code is contributed by avanitrachhadiya2155</script> |
Output
17
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!