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 ' .
$ prime = array_fill ( 0 , $ n + 1 , 0 ) ; $ sum = 0 ; $ max = ( int ) ( $ n / 2 ) ; for ( $ p = 2 ; $ p <= $ max ; $ p ++ ) {