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// powersvector<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 codeint 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// powersstatic 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 codepublic 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 mathMAX = 100001class pair: def __init__(self, f, s): self.F = f self.S = s# To store prime factors and their# powersfactors = [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 codefor 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// powersstatic 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 codepublic 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// powerslet 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 codefor (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)
If you like neveropen and would like to contribute, you can also write an article using write.geeksforgeeks.org or mail your article to review-team@geeksforgeeks.org. See your article appearing on the neveropen main page and help other Geeks.
Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
