Sum of Factors of a Number using Prime Factorization | Using SieveOfEratosthenes to find smallest prime factor of all the numbers . For example , if N is 10 , s [ 2 ] = s [ 4 ] = s [ 6 ] = s [ 10 ] = 2 s [ 3 ] = s [ 9 ] = 3 s [ 5 ] = 5 s [ 7 ] = 7 ; Create a boolean array " prime [ 0 . . n ] " and initialize all entries in it as false . ; Initializing smallest factor equal to 2 for all the even numbers ; 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 find sum of all prime factors ; Declaring array to store smallest prime factor of i at i - th index ; Filling values in s [ ] using sieve ; Current prime factor of N ; Power of current prime factor ; N is now N / s [ N ] . If new N als has smallest prime factor as currFactor , increment power ; Update current prime factor as s [ N ] and initializing power of factor as 1. ; Driver code
< ? php function sieveOfEratosthenes ( $ N , & $ s ) { $ prime = array_fill ( 0 , $ N + 1 , false ) ; for ( $ i = 2 ; $ i <= $ N ; $ i += 2 ) $ s [ $ i ] = 2 ; for ( $ i = 3 ; $ i <= $ N ; $ i += 2 ) { if ( $ prime [ $ i ] == false ) { $ s [ $ i ] = $ i ; for ( $ j = $ i ; $ j * $ i <= $ N ; $ j += 2 ) { if ( $ prime [ $ i * $ j ] == false ) { $ prime [ $ i * $ j ] = true ; $ s [ $ i * $ j ] = $ i ; } } } } } function findSum ( $ N ) { $ s = array_fill ( 0 , $ N + 1 , 0 ) ; $ ans = 1 ; sieveOfEratosthenes ( $ N , $ s ) ; $ currFactor = $ s [ $ N ] ; $ power = 1 ; while ( $ N > 1 ) { $ N /= $ s [ $ N ] ; if ( $ currFactor == $ s [ $ N ] ) { $ power ++ ; continue ; } $ sum = 0 ; for ( $ i = 0 ; $ i <= $ power ; $ i ++ ) $ sum += ( int ) pow ( $ currFactor , $ i ) ; $ ans *= $ sum ; $ currFactor = $ s [ $ N ] ; $ power = 1 ; } return $ ans ; } $ n = 12 ; echo " Sum ▁ of ▁ the ▁ factors ▁ is ▁ : ▁ " ; echo findSum ( $ n ) ; ? >