Given a number N, the task is to find the sum of all the prime factors of N.
Examples:
Input: 10
Output: 7
Explanation: 2, 5 are prime divisors of 10Input: 20
Output: 7
Explanation: 2, 5 are prime divisors of 20
Approach: This problem can be solved by finding all the prime factors of the number. Follow the steps below to solve this problem:
- Initialize a variable sum as 0 to store the sum of prime divisors of N.
- If N is divisible by 2, add 2 to sum and divide N by 2 until it is divisible.
- Iterate in the range [3, sqrt(N)] using the variable i, with an increment of 2:
- If N is divisible by i, add i to sum and divide N by i until it is divisible.
- If N is a prime number greater than 2, add N to sum.
- After completing the above steps, print the sum as the answer.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to find sum of prime// divisors of the given number Nint SumOfPrimeDivisors(int n){ int sum = 0; // Add the number 2 if it divides N if (n % 2 == 0) { sum = sum + 2; } while (n % 2 == 0) { n = n / 2; } // Traverse the loop from [3, sqrt(N)] for (int i = 3; i <= sqrt(n); i = i + 2) { // If i divides N, add i and divide N if (n % i == 0) { sum = sum + i; } while (n % i == 0) { n = n / i; } } // This condition is to handle the case when N // is a prime number greater than 2 if (n > 2) { sum = sum + n; } return sum;}// Driver codeint main(){ // Given Input int n = 10; // Function Call cout << SumOfPrimeDivisors(n); return 0;} |
Java
// Java program for the above approachimport java.io.*;class GFG { // Function to find sum of prime // divisors of the given number N public static int SumOfPrimeDivisors(int n) { int sum = 0; // Add the number 2 if it divides N if (n % 2 == 0) { sum = sum + 2; } while (n % 2 == 0) { n = n / 2; } // Traverse the loop from [3, sqrt(N)] for (int i = 3; i <= Math.sqrt(n); i = i + 2) { // If i divides N, add i and divide N if (n % i == 0) { sum = sum + i; } while (n % i == 0) { n = n / i; } } // This condition is to handle the case when N // is a prime number greater than 2 if (n > 2) { sum = sum + n; } return sum; } // Driver code public static void main (String[] args) { // Given Input int n = 10; // Function Call System.out.println(SumOfPrimeDivisors(n)); }}// This code is contributed by Potta Lokesh |
Python3
# Python3 program for the above approachimport math# Function to find sum of prime# divisors of the given number Ndef SumOfPrimeDivisors(n): sum = 0 # Add the number 2 if it divides N if n % 2 == 0: sum += 2 while n % 2 == 0: n //= 2 # Traverse the loop from [3, sqrt(N)] k = int(math.sqrt(n)) for i in range(3, k + 1, 2): # If i divides N, add i and divide N if n % i == 0: sum += i while n % i == 0: n //= i # This condition is to handle the case when N # is a prime number greater than 2 if n > 2: sum += n # Return the sum return sum# Driver codeif __name__ == '__main__': # Given input n = 10 # Function call print(SumOfPrimeDivisors(n)) # This code is contributed by MuskanKalra1 |
C#
// C# program for the above approachusing System;class GFG { // Function to find sum of prime // divisors of the given number N public static int SumOfPrimeDivisors(int n) { int sum = 0; // Add the number 2 if it divides N if (n % 2 == 0) { sum = sum + 2; } while (n % 2 == 0) { n = n / 2; } // Traverse the loop from [3, sqrt(N)] for (int i = 3; i <= Math.Sqrt(n); i = i + 2) { // If i divides N, add i and divide N if (n % i == 0) { sum = sum + i; } while (n % i == 0) { n = n / i; } } // This condition is to handle the case when N // is a prime number greater than 2 if (n > 2) { sum = sum + n; } return sum; } // Driver code public static void Main (String[] args) { // Given Input int n = 10; // Function Call Console.Write(SumOfPrimeDivisors(n)); }}// This code is contributed by shivanisinghss2110 |
Javascript
<script> // JavaScript program for the above approach // Function to find sum of prime // divisors of the given number N function SumOfPrimeDivisors(n) { let sum = 0; // Add the number 2 if it divides N if (n % 2 == 0) { sum = sum + 2; } while (n % 2 == 0) { n = n / 2; } // Traverse the loop from [3, sqrt(N)] for (let i = 3; i <= Math.sqrt(n); i = i + 2) { // If i divides N, add i and divide N if (n % i == 0) { sum = sum + i; } while (n % i == 0) { n = n / i; } } // This condition is to handle the case when N // is a prime number greater than 2 if (n > 2) { sum = sum + n; } return sum; } // Driver code // Given Input let n = 10; // Function Call document.write(SumOfPrimeDivisors(n));// This code is contributed by Potta Lokesh </script> |
Output
7
Time complexity: O(sqrt(N))
Auxiliary Space: O(1)
Approach: Using Sieve of Eratosthenes
Steps:
- Start by defining a function sumOfPrimeFactors that takes an integer N as input and returns the sum of its prime factors.
- Create a vector isPrime of size N+1 and initialize all elements as true.
- Next, iterate from 2 to the square root of N using a variable p.
- After generating the list of prime numbers, initialize a variable sum as 0 and store the sum of the prime factors of N.
- Next, iterate from 2 to N and check if the number is a prime factor of N and is also a prime number according to the isPrime vector. If the number is a prime factor, add it to the sum.
- Aso, divide N by the prime factor until it’s no longer divisible by that factor. This step ensures that we only count each prime factor once in the sum.
- Finally, return the sum as the result.
Below is the implementation of the above approach:
C++
// C++ program of the aobe approach#include <iostream>#include <vector>using namespace std;// Function to find the sum of prime factors using Sieve of// Eratosthenesint sumOfPrimeFactors(int N){ // Generate a list of primes up to the square root of N vector<bool> isPrime(N + 1, true); for (int p = 2; p * p <= N; p++) { if (isPrime[p]) { for (int i = p * p; i <= N; i += p) { isPrime[i] = false; } } } // Compute the sum of prime factors int sum = 0; for (int p = 2; p <= N; p++) { if (isPrime[p] && N % p == 0) { sum += p; while (N % p == 0) { N /= p; } } } return sum;}// Driver Codeint main(){ int N = 10; int sum = sumOfPrimeFactors(N); cout << sum << endl; return 0;} |
Java
import java.util.Arrays;public class Main { // Function to find the sum of prime factors using Sieve of Eratosthenes static int sumOfPrimeFactors(int N) { // Generate a list of primes up to the square root of N boolean[] isPrime = new boolean[N + 1]; Arrays.fill(isPrime, true); for (int p = 2; p * p <= N; p++) { if (isPrime[p]) { for (int i = p * p; i <= N; i += p) { isPrime[i] = false; } } } // Compute the sum of prime factors int sum = 0; for (int p = 2; p <= N; p++) { if (isPrime[p] && N % p == 0) { sum += p; while (N % p == 0) { N /= p; } } } return sum; } // Driver Code public static void main(String[] args) { int N = 10; int sum = sumOfPrimeFactors(N); System.out.println(sum); }} |
Python3
def sumOfPrimeFactors(N): # Generate a list of primes up to the square root of N isPrime = [True] * (N + 1) p = 2 while p * p <= N: if isPrime[p]: for i in range(p * p, N + 1, p): isPrime[i] = False p += 1 # Compute the sum of prime factors sum = 0 p = 2 while p <= N: if isPrime[p] and N % p == 0: sum += p while N % p == 0: N //= p p += 1 return sum# Driver Codeif __name__ == "__main__": N = 10 sum_result = sumOfPrimeFactors(N) print(sum_result) |
C#
using System;class Program{ // Function to find the sum of prime factors static int SumOfPrimeFactors(int N) { // Generate a list of primes up to the square root of N bool[] isPrime = new bool[N + 1]; // Initialize all numbers as potentially prime for (int i = 2; i <= N; i++) { isPrime[i] = true; } // Use the Sieve of Eratosthenes algorithm to mark non-prime numbers for (int p = 2; p * p <= N; p++) { if (isPrime[p]) { for (int i = p * p; i <= N; i += p) { isPrime[i] = false; } } } // Compute the sum of prime factors int sum = 0; for (int p = 2; p <= N; p++) { if (isPrime[p] && N % p == 0) { sum += p; // Continue to divide N by p until it's no longer divisible while (N % p == 0) { N /= p; } } } return sum; } static void Main() { int N = 10; // Call the SumOfPrimeFactors function with N as the input int sum = SumOfPrimeFactors(N); // Output the sum of prime factors Console.WriteLine("Sum of prime factors of " + N + " is: " + sum); }} |
Output:
7
Time Complexity: O(N * log(log N)),
Auxiliary Space: O(N)
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!
