Sum of all proper divisors of natural numbers in an array | C ++ 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; #define MAX  1000001 NEW_LINE #define pii  pair<int, int> NEW_LINE #define F  first NEW_LINE #define S  second NEW_LINE vector < pii > factors [ MAX ] ; void sieveOfEratothenese ( ) { bool isPrime [ MAX ] ; memset ( isPrime , true , sizeof ( isPrime ) ) ; 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 ] . push_back ( make_pair ( i , l ) ) ; } } } } int sumOfProperDivisors ( int num ) { int mul = 1 ; for ( int i = 0 ; i < factors [ num ] . size ( ) ; i ++ ) mul *= ( ( pow ( factors [ num ] [ i ] . F , factors [ num ] [ i ] . S + 1 ) - 1 ) / ( factors [ num ] [ i ] . F - 1 ) ) ; return mul - num ; } int main ( ) { sieveOfEratothenese ( ) ; int arr [ ] = { 8 , 13 , 24 , 36 , 59 , 75 , 91 } ; for ( int i = 0 ; i < sizeof ( arr ) / sizeof ( int ) ; i ++ ) cout << sumOfProperDivisors ( arr [ i ] ) << " ▁ " ; cout << endl ; return 0 ; }