Sum of all proper divisors of natural numbers in an array | Java program to find sum of proper divisors for every element in an array . ; To store prime factors and their powers ; Fills factors such that factors [ i ] is a vector of pairs containing prime factors ( of i ) and their powers . Also sets values in isPrime [ ] ; To check if a number is prime ; If i is prime , then update its powers in all multiples of it . ; Returns sum of proper divisors of num using factors [ ] ; Applying above discussed formula for every array element ; Driver code
import java . util . * ; class GFG { static final int MAX = 100001 ; static class pair { int F , S ; public pair ( int f , int s ) { F = f ; S = s ; } } static Vector < pair > [ ] factors = new Vector [ MAX ] ; static void sieveOfEratothenese ( ) { boolean [ ] isPrime = new boolean [ MAX ] ; Arrays . fill ( isPrime , true ) ; isPrime [ 0 ] = isPrime [ 1 ] = false ; for ( int i = 2 ; i < MAX ; i ++ ) { if ( isPrime [ i ] ) { for ( int j = i ; j < MAX ; j += i ) { int k , l ; isPrime [ j ] = false ; for ( k = j , l = 0 ; k % i == 0 ; l ++ , k /= i ) ; factors [ j ] . add ( new pair ( i , l ) ) ; } } } } static int sumOfProperDivisors ( int num ) { int mul = 1 ; for ( int i = 0 ; i < factors [ num ] . size ( ) ; i ++ ) mul *= ( ( Math . pow ( factors [ num ] . get ( i ) . F , factors [ num ] . get ( i ) . S + 1 ) - 1 ) / ( factors [ num ] . get ( i ) . F - 1 ) ) ; return mul - num ; } public static void main ( String [ ] args ) { for ( int i = 0 ; i < MAX ; i ++ ) factors [ i ] = new Vector < pair > ( ) ; sieveOfEratothenese ( ) ; int arr [ ] = { 8 , 13 , 24 , 36 , 59 , 75 , 91 } ; for ( int i = 0 ; i < arr . length ; i ++ ) System . out . print ( sumOfProperDivisors ( arr [ i ] ) + " ▁ " ) ; System . out . println ( ) ; } }