Sum of Factors of a Number using Prime Factorization | Java Program to find sum of all factors of a given number ; 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
public class GFG { static void sieveOfEratosthenes ( int N , int s [ ] ) { boolean [ ] prime = new boolean [ N + 1 ] ; for ( int i = 0 ; i < N + 1 ; i ++ ) prime [ i ] = false ; for ( int i = 2 ; i <= N ; i += 2 ) s [ i ] = 2 ; for ( int i = 3 ; i <= N ; i += 2 ) { if ( prime [ i ] == false ) { s [ i ] = i ; for ( int j = i ; j * i <= N ; j += 2 ) { if ( prime [ i * j ] == false ) { prime [ i * j ] = true ; s [ i * j ] = i ; } } } } } static int findSum ( int N ) { int [ ] s = new int [ N + 1 ] ; int ans = 1 ; sieveOfEratosthenes ( N , s ) ; int currFactor = s [ N ] ; int power = 1 ; while ( N > 1 ) { N /= s [ N ] ; if ( currFactor == s [ N ] ) { power ++ ; continue ; } int sum = 0 ; for ( int i = 0 ; i <= power ; i ++ ) sum += Math . pow ( currFactor , i ) ; ans *= sum ; currFactor = s [ N ] ; power = 1 ; } return ans ; } public static void main ( String [ ] args ) { int n = 12 ; System . out . print ( " Sum ▁ of ▁ the ▁ factors ▁ is ▁ : ▁ " ) ; System . out . print ( findSum ( n ) ) ; } }