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