Sum of Factors

We will iterate from 1 to ‘N’, and if the current number is a factor of ‘N’, we will add it to our answer.

Algorithm:
 

1. Declare a variable ‘SUM’ of type integer, and initialize it with zero.
2. Start iterating from 1 to ‘N’.
   1. If the current iterator ( say i ) is a factor of ‘N’ ( N % i == 0 ), then add it to the ‘SUM’.
3. Finally, return ‘SUM’.

We can observe that the factors of any integer come in pairs. For each factor ‘D1’ such that 1 <= ‘D1’ <= sqrt(‘N’) , there will be another factor ‘D2’ = ‘N’ / ‘D1’ such that sqrt(‘N’) <= ‘D2’ <= ‘N’. But we have to be careful when ‘D1’ is equal to ‘D2’. In that case, we will consider ‘D1’ only once.

We will iterate from 1 to sqrt(‘N’). For each factor of ‘N’, we will also consider the other factor ‘N’ / ‘i’ and add them to the answer.

Algorithm:
 

1. Declare a variable ‘SUM’ and initialize it with zero.
2. Start iterating from 1 to sqrt(‘N’).
3. If the current iterator ( say ‘i’ ) is a divisor of ‘N’ ( ‘N’ % ‘i’ == 0 ):
   1. If i is not equal to sqrt(‘N’):
      1. Add ’i’ to the  ‘SUM’.
      2. Add ‘N’ / ‘i’ to the ‘SUM’.
   2. Else:
      1. Add ‘i’ to the ‘SUM’.
4. Finally, return the ‘SUM’.

Let ‘p1’,’p2’,....,’ pm’ be the prime factors of a number ‘N’, and let ‘a1’,’a2’,....,’am’ be the highest powers of the prime factors respectively, then the sum of all the factors can be written as:

‘SUM’ = ( 1 + p1 + p1^2 + …. + p1^a1) * ( 1 + p2 + p2^2 + …. + p2^a2) * …. * ( 1 + pm + pm^2 + …. + pm^am).

So now we will implement this to solve our problem.

Algorithm:

1. Declare a variable ‘SUM’ and initialize it with zero.
2. Start iterating from 2 to sqrt(‘N’).
   1. Declare two variables, ‘TempSum’ and ‘TempFactor’, and initialize with 1.
   2. Now using a while loop, we will count the highest power ‘ai’ of that particular number ‘i’ and store the sum of the powers in the ‘TempSum’.
3. Now multiply the ‘TempSum’ with the ‘SUM” variable.
4. Check the case of prime number since the above for loop will not consider this.
5. Finally, return the ‘SUM’ variable.

We will use the Sieve of Eratosthenes to precompute the sum of all the divisors for each possible integer and store it in the ‘sum’ array. Then we can just take the required elements from the ‘sum’ array.

More details about the Sieve of Eratosthenes can be found at the given link:

https://cp-algorithms.com/algebra/sieve-of-eratosthenes.html
 

Algorithm:

1. preCompute function:
   1. It will take the ‘sum’ vector as an argument and store the sum of all the divisors up to ‘maxN’ to the vector.
   2. First we will iterate from 1 to ‘maxN’.
   3. For each iterator ‘i’, add it to all the numbers whose one of the divisors is ‘i’.
2. given function:
   1. Declare the ‘sum’ vector and precompute all the values using the ‘preCompute’ function.
   2. Then iterate through the given array and store the corresponding result in the ‘ans’ array.
   3. Finally, return the ‘ans’ vector.