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 list " 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 list to store smallest prime factor of i at i - th index ; Filling values in s [ ] using sieve function calling ; Current prime factor of N ; Power of current prime factor ; N is now Ns [ N ] . If new N also has smallest prime factor as currFactor , increment power ; Update current prime factor as s [ N ] and initializing power of factor as 1. ; Driver Code
def sieveOfEratosthenes ( N , s ) : NEW_LINE INDENT prime = [ False ] * ( N + 1 ) NEW_LINE for i in range ( 2 , N + 1 , 2 ) : NEW_LINE INDENT s [ i ] = 2 NEW_LINE DEDENT for i in range ( 3 , N + 1 , 2 ) : NEW_LINE INDENT if prime [ i ] == False : NEW_LINE INDENT s [ i ] = i NEW_LINE for j in range ( i , ( N + 1 ) // i , 2 ) : NEW_LINE INDENT if prime [ i * j ] == False : NEW_LINE INDENT prime [ i * j ] = True NEW_LINE s [ i * j ] = i NEW_LINE DEDENT DEDENT DEDENT DEDENT DEDENT def findSum ( N ) : NEW_LINE INDENT s = [ 0 ] * ( N + 1 ) NEW_LINE ans = 1 NEW_LINE sieveOfEratosthenes ( N , s ) NEW_LINE currFactor = s [ N ] NEW_LINE power = 1 NEW_LINE while N > 1 : NEW_LINE INDENT N //= s [ N ] NEW_LINE if currFactor == s [ N ] : NEW_LINE INDENT power += 1 NEW_LINE continue NEW_LINE DEDENT sum = 0 NEW_LINE for i in range ( power + 1 ) : NEW_LINE INDENT sum += pow ( currFactor , i ) NEW_LINE DEDENT ans *= sum NEW_LINE currFactor = s [ N ] NEW_LINE power = 1 NEW_LINE DEDENT return ans NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT n = 12 NEW_LINE print ( " Sum ▁ of ▁ the ▁ factors ▁ is ▁ : " , end = " ▁ " ) NEW_LINE print ( findSum ( n ) ) NEW_LINE DEDENT