Sum of largest prime factor of each number less than equal to n | Java implementation to find sum of largest prime factor of each number less than equal to n ; function to find sum of largest prime factorof 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
import java . io . * ; import java . util . * ; class GFG { static int sumOfLargePrimeFactor ( int n ) { int prime [ ] = new int [ n + 1 ] , sum = 0 ; Arrays . fill ( prime , 0 ) ; 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 ] != 0 ) sum += prime [ p ] ; else sum += p ; } return sum ; } public static void main ( String args [ ] ) { int n = 12 ; System . out . println ( " Sum ▁ = ▁ " + sumOfLargePrimeFactor ( n ) ) ; } }