Sum of all proper divisors of natural numbers in an array
Given an array of natural numbers count the sum of its proper divisors for every element in array.
Example:
Input : int arr[] = {8, 13, 24, 36, 59, 75, 87} Output : 7 1 36 55 1 49 21 Number 8 has 3 proper divisors 1, 2, 4 and their sum comes out to be 7.
A naive solution to this problem has been discussed in below post.
Sum of all proper divisors of a natural number
We can do this more efficiently by making use of sieve of Eratosthenes.
The idea is based on prime factorization of a number. By using sieve we can store all the prime factors of a number and their powers.
To find all divisors, we need to consider all powers of a prime factor and multiply it with all powers of other prime factors. (For example, if the number is 36, its prime factors are 2 and 3 and all divisors are 1, 2, 3, 4, 6, 9, 12 and 18. Consider a number N can be written as P1^Q1 * P2^Q2 * P3^Q3 (here only 3 prime factors are considered but there can be more than that) then sum of its divisors will be written as: = P1^0 * P2^0 * P3^0 + P1^0 * P2^0 * P3^1 + P1^0 * P2^0 * P3^2 + ................ + P1^0 * P2^0 * P3^Q3 + P1^0 * P2^1 * P3^0 + P1^0 * P2^1 * P3^1 + P1^0 * P2^1 * P3^2 + ................ + P1^0 * P2^1 * P3^Q3 + . . . P1^Q1 * P2^Q2 * P3^0 + P1^Q1 * P2^Q2 * P3^1 + P1^Q1 * P2^Q2 * P3^2 + .......... + P1^Q1 * P2^Q2 * P3^Q3 Above can be written as, (((P1^(Q1+1)) - 1) / (P1 - 1)) * (((P2^(Q2+1)) - 1) / (P2 - 1)) * (((P3^(Q3 + 1)) - 1) / (P3 - 1))
Below is implementation based on above formula.
C++
// C++ program to find sum of proper divisors for // every element in an array. #include <bits/stdc++.h> using namespace std; #define MAX 1000001 #define pii pair<int, int> #define F first #define S second // To store prime factors and their // powers vector<pii> factors[MAX]; // Fills factors such that factors[i] is // a vector of pairs containing prime factors // (of i) and their powers. // Also sets values in isPrime[] void sieveOfEratothenese() { // To check if a number is prime bool isPrime[MAX]; memset (isPrime, true , sizeof (isPrime)); isPrime[0] = isPrime[1] = false ; for ( int i = 2; i < MAX; i++) { // If i is prime, then update its // powers in all multiples of it. 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)); } } } } // Returns sum of proper divisors of num // using factors[] int sumOfProperDivisors( int num) { // Applying above discussed formula for every // array element 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; } // Driver code 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; } |
Java
// Java program to find sum of proper divisors for // every element in an array. 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; } } // To store prime factors and their // powers static Vector<pair> []factors = new Vector[MAX]; // Fills factors such that factors[i] is // a vector of pairs containing prime factors // (of i) and their powers. // Also sets values in isPrime[] static void sieveOfEratothenese() { // To check if a number is prime boolean []isPrime = new boolean [MAX]; Arrays.fill(isPrime, true ); isPrime[ 0 ] = isPrime[ 1 ] = false ; for ( int i = 2 ; i < MAX; i++) { // If i is prime, then update its // powers in all multiples of it. 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)); } } } } // Returns sum of proper divisors of num // using factors[] static int sumOfProperDivisors( int num) { // Applying above discussed formula for every // array element 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; } // Driver code 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(); } } // This code is contributed by 29AjayKumar |
Python3
# Python program to find sum of proper divisors for # every element in an array. import math MAX = 100001 class pair: def __init__( self , f, s): self .F = f self .S = s # To store prime factors and their # powers factors = [ 0 for i in range ( MAX )] # Fills factors such that factors[i] is # a vector of pairs containing prime factors # (of i) and their powers. # Also sets values in isPrime[] def sieveOfEratothenese(): # To check if a number is prime global MAX isPrime = [ 0 for i in range ( MAX )] for i in range ( MAX ): isPrime[i] = True isPrime[ 0 ] = isPrime[ 1 ] = False for i in range ( 2 , MAX ): # If i is prime, then update its # powers in all multiples of it. if (isPrime[i]): for j in range (i, MAX ,i): isPrime[j] = False k = j l = 0 while (k % i = = 0 ): l + = 1 k = k / / i factors[j].append(pair(i, l)) # Returns sum of proper divisors of num # using factors[] def sumOfProperDivisors(num): # Applying above discussed formula for every # array element mul = 1 for i in range ( len (factors[num])): mul * = math.floor((math. pow (factors[num][i].F,factors[num][i].S + 1 ) - 1 ) / / (factors[num][i].F - 1 )) return mul - num # Driver code for i in range ( MAX ): factors[i] = [] sieveOfEratothenese() arr = [ 8 , 13 , 24 , 36 , 59 , 75 , 91 ] for i in range ( len (arr)): print (sumOfProperDivisors(arr[i]), end = " " ) print () # This code is contributed by shinjanpatra |
C#
// C# program to find sum of proper divisors for // every element in an array. using System; using System.Collections.Generic; class GFG { static readonly int MAX = 100001; class pair { public int F, S; public pair( int f, int s) { F = f; S = s; } } // To store prime factors and their // powers static List<pair> []factors = new List<pair>[MAX]; // Fills factors such that factors[i] is // a vector of pairs containing prime factors // (of i) and their powers. // Also sets values in isPrime[] static void sieveOfEratothenese() { // To check if a number is prime bool []isPrime = new bool [MAX]; for ( int i = 0; i < MAX; i++) isPrime[i] = true ; isPrime[0] = isPrime[1] = false ; for ( int i = 2; i < MAX; i++) { // If i is prime, then update its // powers in all multiples of it. 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)); } } } } // Returns sum of proper divisors of num // using factors[] static int sumOfProperDivisors( int num) { // Applying above discussed formula for every // array element int mul = 1; for ( int i = 0; i < factors[num].Count; i++) mul *= ( int )((Math.Pow(factors[num][i].F, factors[num][i].S + 1) - 1) / (factors[num][i].F - 1)); return mul - num; } // Driver code public static void Main(String[] args) { for ( int i = 0; i < MAX; i++) factors[i] = new List<pair>(); sieveOfEratothenese(); int []arr = { 8, 13, 24, 36, 59, 75, 91 }; for ( int i = 0; i < arr.Length; i++) Console.Write(sumOfProperDivisors(arr[i])+ " " ); Console.WriteLine(); } } // This code is contributed by 29AjayKumar |
Javascript
<script> // JavaScript program to find sum of proper divisors for // every element in an array. let MAX = 100001; class pair { constructor(f,s) { this .F = f; this .S = s; } } // To store prime factors and their // powers let factors = new Array(MAX); // Fills factors such that factors[i] is // a vector of pairs containing prime factors // (of i) and their powers. // Also sets values in isPrime[] function sieveOfEratothenese() { // To check if a number is prime let isPrime = new Array(MAX); for (let i=0;i<MAX;i++) { isPrime[i]= true ; } isPrime[0] = isPrime[1] = false ; for (let i = 2; i < MAX; i++) { // If i is prime, then update its // powers in all multiples of it. if (isPrime[i]) { for (let j = i; j < MAX; j += i) { let k, l; isPrime[j] = false ; for (k = j, l = 0; k % i == 0; l++, k = Math.floor(k/i)) ; factors[j].push( new pair(i, l)); } } } } // Returns sum of proper divisors of num // using factors[] function sumOfProperDivisors(num) { // Applying above discussed formula for every // array element let mul = 1; for (let i = 0; i < factors[num].length; i++) mul *= Math.floor((Math.pow(factors[num][i].F, factors[num][i].S + 1) - 1) / (factors[num][i].F - 1)); return mul - num; } // Driver code for (let i = 0; i < MAX; i++) factors[i] = []; sieveOfEratothenese(); let arr = [ 8, 13, 24, 36, 59, 75, 91 ]; for (let i = 0; i < arr.length; i++) document.write(sumOfProperDivisors(arr[i])+ " " ); document.write( "<br>" ); // This code is contributed by rag2127 </script> |
Output:
7 1 36 55 1 49 21
Time Complexity: O(n*log(log(n)))
Auxiliary Space: O(n)
Contact Us