Find the sum of all the numbers between the range l and r. Here each number is represented by the sum of its distinct prime factors.
Examples:
Input: l = 1, r = 6
Output: 17
Explanation: For 1, sum of prime factors = 0
For 2, Sum of Prime factors = 2
For 3, Sum of Prime factors = 3
For 4, Sum of Prime factors = 2
For 5, Sum of Prime factors = 5
For 6, Sum of Prime factors = 2 + 3 = 5
So, Total sum of all prime factors for the given range = 2 + 3 + 2 + 5 + 5 = 17Input: l = 11, r = 15
Output: 46
Explanation: For 11, sum of prime factors = 11
For 12, Sum of Prime factors = 2 + 3 = 5
For 13, Sum of Prime factors = 13
For 14, Sum of Prime factors = 2 + 7 = 9
For 15, Sum of Prime factors = 3 + 5 = 8
So, Total sum of all prime factors for the given range = 11 + 5 + 13 + 9 + 8 = 46
Approach: To solve the problem follow the below steps:
- Create a function to find out all prime factors of a number and sum all prime factors which will represent that number.
- Sum all the modified numbers in the range [l, r] numbers and return that as the total sum.
Below is the implementation of the above approach.
C++
// C++ code to implement the approach#include <bits/stdc++.h>using namespace std;// Function to check primebool isPrime(int x){ if (x == 1) return false; if (x == 2) return true; for (int i = 2; i * i <= x; i++) { // If X has factor that is i, // then return not Prime if (x % i == 0) return false; } // If we reach here means no factor // found so return prime return true;}// This function is to represent a number// as a sum of all its prime factorsint SumOfPrimeFactors(int l, int r){ int sum = 0, ans = 0; for (int i = l; i <= r; i++) { sum = 0; for (int j = 1; j * j <= i; j++) { // If num has factor i and that // also prime if (i % j == 0) { if (isPrime(j)) sum += j; if (i / j != j and isPrime(i / j)) sum += i / j; } } ans += sum; } return ans;}// Driver Codeint main(){ int l = 11, r = 15; // Function call cout << SumOfPrimeFactors(l, r); return 0;} |
Java
// Java code to implement the approachimport java.io.*;class GFG { // Function to check prime static boolean isPrime(int x) { if (x == 1) return false; if (x == 2) return true; for (int i = 2; i * i <= x; i++) { // If X has factor that is i, // then return not Prime if (x % i == 0) return false; } // If we reach here means no factor // found so return prime return true; } // This function is to represent a number // as a sum of all its prime factors static int SumOfPrimeFactors(int l, int r) { int sum = 0, ans = 0; for (int i = l; i <= r; i++) { sum = 0; for (int j = 1; j * j <= i; j++) { // If num has factor i and that // also prime if (i % j == 0) { if (isPrime(j)) { sum += j; } if (i / j != j && isPrime(i / j)) { sum += i / j; } } } ans += sum; } return ans; } public static void main(String[] args) { int l = 11, r = 15; // Function call System.out.print(SumOfPrimeFactors(l, r)); }}// This code is contributed by lokeshmvs21. |
Python3
# python code to implement the approachimport math# Function to check primedef isPrime(x): if (x == 1): return False if (x == 2): return True for i in range(2,int(math.sqrt(x))+1): # If X has factor that is i, # then return not Prime if (x % i == 0): return False # If we reach here means no factor # found so return prime return True# This function is to represent a number# as a sum of all its prime factorsdef SumOfPrimeFactors(l,r): sumvar = 0 ans = 0 #for ( i = l i <= r i++) for i in range(l,r+1): sumvar = 0 # for (int j = 1; j * j <= i; j++) { for j in range(1,int(math.sqrt(i))+1): # If num has factor i and that # also prime if (i % j == 0): if (isPrime(j)): sumvar += j if (int(i / j) != j and isPrime(int(i / j))): sumvar += math.floor(i / j) ans += sumvar return ansl = 11r = 15# Function callprint(SumOfPrimeFactors(l, r))# This code is contributed by ksam24000 |
C#
// C# implementationusing System;public class GFG { // Function to check prime public static bool isPrime(int x) { if (x == 1) return false; if (x == 2) return true; for (int i = 2; i * i <= x; i++) { // If X has factor that is i, // then return not Prime if (x % i == 0) return false; } // If we reach here means no factor // found so return prime return true; } // This function is to represent a number // as a sum of all its prime factors public static int SumOfPrimeFactors(int l, int r) { int sum = 0, ans = 0; for (int i = l; i <= r; i++) { sum = 0; for (int j = 1; j * j <= i; j++) { // If num has factor i and that // also prime if (i % j == 0) { if (isPrime(j) == true) sum += j; if ((int)(i / j) != j && isPrime((int)(i / j))) sum += i / j; } } ans += sum; } return ans; } static public void Main() { int l = 11, r = 15; // Function call Console.WriteLine(SumOfPrimeFactors(l, r)); }}// this code is contributed by ksam24000 |
Javascript
// Javascript code to implement the approach// Function to check primefunction isPrime(x){ if (x == 1) return false; if (x == 2) return true; for (let i = 2; i * i <= x; i++) { // If X has factor that is i, // then return not Prime if (x % i == 0) return false; } // If we reach here means no factor // found so return prime return true;}// This function is to represent a number// as a sum of all its prime factorsfunction SumOfPrimeFactors(l, r){ let sum = 0, ans = 0; for (let i = l; i <= r; i++) { sum = 0; for (let j = 1; j * j <= i; j++) { // If num has factor i and that // also prime if (i % j == 0) { if (isPrime(j)) sum += j; if (i / j != j && isPrime(i / j)) sum += i / j; } } ans += sum; } return ans;}// Driver Codelet l = 11, r = 15;// Function callconsole.log(SumOfPrimeFactors(l, r));// This code is contributed by Samim Hossain Mondal. |
46
Time Complexity: O(N * sqrt(r) * sqrt(r)) where n is the number of elements in the range and it takes maximum sqrt(r) time each to find all the factors and check if the factors are prime.
Auxiliary Space: O(1)
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!
