Find sum of exponents of prime factors of numbers 1 to N

0 0 8 minutes read

Given an integer N, the task is to find the sum of exponents of prime factors of numbers 1 to N.

Examples:

Input: N = 4
Output: 4
Explanation:
Numbers up to 4 are 1, 2, 3, 4 where
The exponent of 1 in the prime factorization of 1 is 0 (2⁰),
For 2 it is 1 (2¹),
For 3 it is 1 (3¹), and
For 4 it is 2 (2²).
The sum of the exponent of prime factors of each number up to 4 is 0 + 1 + 1 + 2 = 4.

Input: N = 10
Output: 15
Explanation:
sum of the exponent of prime factors of each number up to 10 is 15.

Approach: The idea is to use the concept of Prime factors and their powers. Below are the steps:

Iterate for each number from 2 to N and for each number do the following:
1. find the power of prime factors for each number N.
2. Find the summation of each power in the above steps
Print the summation of all the powers of prime factors of N and print the sum.

Below is the implementation of the above approach:

C++

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to implement sieve of
// eratosthenes
void sieveOfEratosthenes(int N, int s[])
{
    // Create a boolean array and
    // initialize all entries as false
    vector<bool> prime(N + 1, false);
 
    // Initializing smallest
    // factor equal to 2
    // for all the even numbers
    for (int i = 2; i <= N; i += 2)
        s[i] = 2;
 
    // Iterate for odd numbers
    // less than equal to n
    for (int i = 3; i <= N; i += 2) {
 
        if (prime[i] == false) {
 
            // s(i) for a prime is
            // the number itself
            s[i] = i;
 
            // For all multiples of
            // current prime number
            for (int j = i;
                 j * i <= N; j += 2) {
 
                if (prime[i * j] == false) {
                    prime[i * j] = true;
 
                    // i is the smallest
                    // prime factor for
                    // number "i*j"
                    s[i * j] = i;
                }
            }
        }
    }
}
 
// Function to generate prime
// factors and its power
int generatePrimeFactors(int N)
{
    // s[i] is going to store
    // smallest prime factor of i
    int s[N + 1];
    int sum = 0;
 
    sieveOfEratosthenes(N, s);
 
    // Current prime factor of N
    int curr = s[N];
 
    // Power of current prime factor
    int cnt = 1;
 
    // Calculating prime factors
    // and their powers sum
    while (N > 1) {
 
        N /= s[N];
 
        if (curr == s[N]) {
 
            // Increment the count and
            // continue the process
            cnt++;
            continue;
        }
 
        // Add count to the sum
        sum = sum + cnt;
 
        curr = s[N];
 
        // Reinitialize count
        cnt = 1;
    }
 
    // Return the result
    return sum;
}
 
// Function to find the sum of all the
// power of prime factors of N
void findSum(int N)
{
 
    int sum = 0;
 
    // Iterate for in [2, N]
    for (int i = 2; i <= N; i++) {
        sum += generatePrimeFactors(i);
    }
    cout << sum << endl;
}
 
// Driver Code
int main()
{
    // Given Number N
    int N = 4;
 
    // Function Call
    findSum(N);
    return 0;
}

Java

// Java program for the above approach 
import java.io.*;
public class GFG{ 
 
// Function to implement sieve of 
// eratosthenes 
static void sieveOfEratosthenes(int N, int s[]) 
{ 
    // Create a boolean array and 
    // initialize all entries as false 
    boolean []prime = new boolean[N + 1];
 
    // Initializing smallest 
    // factor equal to 2 
    // for all the even numbers 
    for(int i = 2; i <= N; i += 2) 
        s[i] = 2; 
 
    // Iterate for odd numbers 
    // less than equal to n 
    for(int i = 3; i <= N; i += 2) 
    { 
        if (prime[i] == false)
        { 
 
            // s(i) for a prime is 
            // the number itself 
            s[i] = i; 
 
            // For all multiples of 
            // current prime number 
            for(int j = i; 
                    j * i <= N; j += 2)
            {
                if (prime[i * j] == false) 
                { 
                    prime[i * j] = true; 
 
                    // i is the smallest 
                    // prime factor for 
                    // number "i*j" 
                    s[i * j] = i; 
                } 
            } 
        } 
    } 
} 
 
// Function to generate prime 
// factors and its power 
static int generatePrimeFactors(int N) 
{ 
    // s[i] is going to store 
    // smallest prime factor of i 
    int []s = new int[N + 1]; 
    int sum = 0; 
 
    sieveOfEratosthenes(N, s); 
 
    // Current prime factor of N 
    int curr = s[N]; 
 
    // Power of current prime factor 
    int cnt = 1; 
 
    // Calculating prime factors 
    // and their powers sum 
    while (N > 1) 
    { 
        N /= s[N]; 
 
        if (curr == s[N])
        { 
 
            // Increment the count and 
            // continue the process 
            cnt++; 
            continue; 
        } 
 
        // Add count to the sum 
        sum = sum + cnt; 
 
        curr = s[N]; 
 
        // Reinitialize count 
        cnt = 1; 
    } 
 
    // Return the result 
    return sum; 
} 
 
// Function to find the sum of all the 
// power of prime factors of N 
static void findSum(int N) 
{ 
    int sum = 0; 
 
    // Iterate for in [2, N] 
    for(int i = 2; i <= N; i++)
    { 
        sum += generatePrimeFactors(i); 
    } 
    System.out.print(sum + "\n"); 
} 
 
// Driver Code 
public static void main(String[] args) 
{ 
    // Given Number N 
    int N = 4; 
 
    // Function Call 
    findSum(N); 
}
}
 
// This code is contributed by Ajay Kumar

Python3

# Python3 program for the above approach 
 
# Function to implement sieve of 
# eratosthenes 
def sieveOfEratosthenes(N, s):
 
    # Create a boolean array and 
    # initialize all entries as false 
    prime = [False] * (N + 1)
 
    # Initializing smallest 
    # factor equal to 2 
    # for all the even numbers
    for i in range(2, N + 1, 2):
        s[i] = 2
 
    # Iterate for odd numbers 
    # less than equal to n 
    for i in range(3, N + 1, 2):
        if (prime[i] == False):
 
            # s(i) for a prime is 
            # the number itself 
            s[i] = i
 
            # For all multiples of 
            # current prime number 
            j = i
            while (j * i <= N):
                if (prime[i * j] == False):
                    prime[i * j] = True
 
                    # i is the smallest 
                    # prime factor for 
                    # number "i*j" 
                    s[i * j] = i
 
                j += 2
 
# Function to generate prime 
# factors and its power 
def generatePrimeFactors(N):
 
    # s[i] is going to store 
    # smallest prime factor of i
    s = [0] * (N + 1)
    sum = 0
 
    sieveOfEratosthenes(N, s)
 
    # Current prime factor of N 
    curr = s[N]
 
    # Power of current prime factor 
    cnt = 1
 
    # Calculating prime factors 
    # and their powers sum 
    while (N > 1):
        N //= s[N]
         
        if (curr == s[N]):
 
            # Increment the count and 
            # continue the process 
            cnt += 1
            continue
 
        # Add count to the sum 
        sum = sum + cnt
 
        curr = s[N] 
 
        # Reinitialize count 
        cnt = 1
 
    # Return the result 
    return sum
 
# Function to find the sum of all the 
# power of prime factors of N 
def findSum (N):
 
    sum = 0
 
    # Iterate for in [2, N] 
    for i in range(2, N + 1):
        sum += generatePrimeFactors(i)
 
    print(sum)
 
# Driver Code
if __name__ == '__main__':
 
    # Given number N
    N = 4
     
    # Function call
    findSum(N)
 
# This code is contributed by himanshu77

C#

// C# program for the above approach 
using System;
 
class GFG{ 
 
// Function to implement sieve of 
// eratosthenes 
static void sieveOfEratosthenes(int N, int []s) 
{ 
     
    // Create a bool array and 
    // initialize all entries as false 
    bool []prime = new bool[N + 1];
     
    // Initializing smallest 
    // factor equal to 2 
    // for all the even numbers 
    for(int i = 2; i <= N; i += 2) 
        s[i] = 2; 
 
    // Iterate for odd numbers 
    // less than equal to n 
    for(int i = 3; i <= N; i += 2) 
    { 
        if (prime[i] == false)
        { 
 
            // s(i) for a prime is 
            // the number itself 
            s[i] = i; 
 
            // For all multiples of 
            // current prime number 
            for(int j = i; 
                    j * i <= N; j += 2)
            {
                if (prime[i * j] == false) 
                { 
                    prime[i * j] = true; 
 
                    // i is the smallest 
                    // prime factor for 
                    // number "i*j" 
                    s[i * j] = i; 
                } 
            } 
        } 
    } 
} 
 
// Function to generate prime 
// factors and its power 
static int generatePrimeFactors(int N) 
{ 
     
    // s[i] is going to store 
    // smallest prime factor of i 
    int []s = new int[N + 1]; 
    int sum = 0; 
 
    sieveOfEratosthenes(N, s); 
 
    // Current prime factor of N 
    int curr = s[N]; 
 
    // Power of current prime factor 
    int cnt = 1; 
 
    // Calculating prime factors 
    // and their powers sum 
    while (N > 1) 
    { 
        N /= s[N]; 
 
        if (curr == s[N])
        { 
             
            // Increment the count and 
            // continue the process 
            cnt++; 
            continue; 
        } 
 
        // Add count to the sum 
        sum = sum + cnt; 
 
        curr = s[N]; 
 
        // Reinitialize count 
        cnt = 1; 
    } 
 
    // Return the result 
    return sum; 
} 
 
// Function to find the sum of all the 
// power of prime factors of N 
static void findSum(int N) 
{ 
    int sum = 0; 
 
    // Iterate for in [2, N] 
    for(int i = 2; i <= N; i++)
    { 
        sum += generatePrimeFactors(i); 
    } 
    Console.Write(sum + "\n"); 
} 
 
// Driver Code 
public static void Main(String[] args) 
{ 
     
    // Given number N 
    int N = 4; 
 
    // Function call 
    findSum(N); 
}
}
 
// This code is contributed by 29AjayKumar

Javascript

<script>
 
// Javascript program for the above approach 
  
// Function to implement sieve of 
// eratosthenes 
function sieveOfEratosthenes(N, s) 
{ 
    // Create a boolean array and 
    // initialize all entries as false 
    let prime = Array.from({length: N+1}, (_, i) => 0);
 
    // Initializing smallest 
    // factor equal to 2 
    // for all the even numbers 
    for(let i = 2; i <= N; i += 2) 
        s[i] = 2; 
 
    // Iterate for odd numbers 
    // less than equal to n 
    for(let i = 3; i <= N; i += 2) 
    { 
        if (prime[i] == false)
        { 
 
            // s(i) for a prime is 
            // the number itself 
            s[i] = i; 
 
            // For all multiples of 
            // current prime number 
            for(let j = i; 
                    j * i <= N; j += 2)
            {
                if (prime[i * j] == false) 
                { 
                    prime[i * j] = true; 
 
                    // i is the smallest 
                    // prime factor for 
                    // number "i*j" 
                    s[i * j] = i; 
                } 
            } 
        } 
    } 
} 
 
// Function to generate prime 
// factors and its power 
function generatePrimeFactors(N) 
{ 
    // s[i] is going to store 
    // smallest prime factor of i 
    let s = Array.from({length: N+1}, (_, i) => 0);
    let sum = 0; 
 
    sieveOfEratosthenes(N, s); 
 
    // Current prime factor of N 
    let curr = s[N]; 
 
    // Power of current prime factor 
    let cnt = 1; 
 
    // Calculating prime factors 
    // and their powers sum 
    while (N > 1) 
    { 
        N /= s[N]; 
 
        if (curr == s[N])
        { 
 
            // Increment the count and 
            // continue the process 
            cnt++; 
            continue; 
        } 
 
        // Add count to the sum 
        sum = sum + cnt; 
 
        curr = s[N]; 
 
        // Reinitialize count 
        cnt = 1; 
    } 
 
    // Return the result 
    return sum; 
} 
 
// Function to find the sum of all the 
// power of prime factors of N 
function findSum(N) 
{ 
    let sum = 0; 
 
    // Iterate for in [2, N] 
    for(let i = 2; i <= N; i++)
    { 
        sum += generatePrimeFactors(i); 
    } 
    document.write(sum + "\n"); 
} 
 
// Driver Code
     
    // Given Number N 
    let N = 4; 
 
    // Function Call 
    findSum(N); 
         
</script>

Output:

Time Complexity: O(N*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 zambiatek!