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
< ? php function sumOfLargePrimeFactor ( $ n ) { $ prime = array_fill ( 0 , $ n + 1 , 0 ) ; $ sum = 0 ; $ max = ( int ) ( $ n / 2 ) ; for ( $ p = 2 ; $ p <= $ max ; $ p ++ ) { if ( $ prime [ $ p ] == 0 ) { for ( $ i = $ p * 2 ; $ i <= $ n ; $ i += $ p ) $ prime [ $ i ] = $ p ; } } for ( $ p = 2 ; $ p <= $ n ; $ p ++ ) { if ( $ prime [ $ p ] ) $ sum += $ prime [ $ p ] ; else $ sum += $ p ; } return $ sum ; } $ n = 12 ; echo " Sum = " ? >