text: Sum of largest prime factor of each number less than equal to n | C ++ implementation to find sum of largest prime factor of each number less than equal to n ; function to find sum of largest prime factor of each number less than equal to n ; Create an integer array " prime [ 0 . . n ] " and initialize all entries of it as 0. A value in prime [ i ] will finally be 0 if ' i ' is a prime , else it will contain the largest prime factor of ' i ' . ; If prime [ p ] is '0' , then it is a prime number ; Update all multiples of p ; Sum up the largest prime factor of all the numbers ; if ' p ' is a non - prime number then prime [ p ] gives its largesr prime factor ; ' p ' is a prime number ; required sum ; Driver program to test above
code: #include <bits/stdc++.h> NEW_LINE using namespace std ; int sumOfLargePrimeFactor ( int n ) { int prime [ n + 1 ] , sum = 0 ; memset ( prime , 0 , sizeof ( prime ) ) ; int max = n / 2 ; for ( int p = 2 ; p <= max ; p ++ ) { if ( prime [ p ] == 0 ) { for ( int i = p * 2 ; i <= n ; i += p ) prime [ i ] = p ; } } for ( int p = 2 ; p <= n ; p ++ ) { if ( prime [ p ] ) sum += prime [ p ] ; else sum += p ; } return sum ; } int main ( ) { int n = 12 ; cout << " Sum ▁ = ▁ " << sumOfLargePrimeFactor ( n ) ; return 0 ; }