Finding sum of divisors of numbers between the range (1 to 1e16)

Question

The exact link to the question : https://www.spoj.com/problems/DIVSUM2/

Input: An integer stating the number of test cases (equal to 500), and that many lines follow, each containing one integer between \$1\$ and \$10^{16}\$ inclusive.

Output: Print one integer, the sum of the proper divisors of the number.

An easier version of this question exists in which the constraints are relaxed.

My code works for the easier version , but exceeds the time limit for the harder one.

Example of approach: \$36=2^2 \times 3^2\$. So sum of proper factors = $$(2^0+2^1+2^2)\times(3^0+3^1+3^2)-36=55$$

My code:

#include<iostream>
long long sum_proper_divisors(long long n)
{
    long long sum=1,x=n;
    for(long long i=2;i*i<=n;i++)
      {
          long long current_sum=1,current_term=1;
           while(n%i==0)
           { 
              n/=i;                 
              current_term*=i;
              current_sum+=current_term;
            }
         sum*=current_sum;
      }
   if(n>=2){
    sum*=(n+1);
    } 
  return (sum-x);
}
int main()
{
   long long q;
   std::cin>>q;
    while(q--)
    {
      long long n;
      std::cin>>n;
      std::cout<<sum_proper_divisors(n)<<std::endl;
    }
 }

Answer 1

What's going on with the indentation?

---

long long

No. We're not in the 1970s. Use <cstdint>. Here you probably want std::uint_fast64_t.

---

IMO n should be const and the copy (x) should be the variable which is modified in the loop.

---

    for(long long i=2;i*i<=n;i++)

The first step to optimising prime divisor searches is to use a wheel. If you special-case i=2 then you can search for(i=3;i*i<=x;i+=2), which is already a speedup by about a factor of 2.

On some architectures, multiplication is expensive and it's faster to maintain a variable ii or iSquared which is updated using the identity \$(i+a)^2 - i^2 = 2ai + a^2\$: e.g. (untested, may be buggy): for(i=3,ii=9;ii<=x;ii+=(i+1)<<2,i+=2)

---

          long long current_sum=1,current_term=1;
           while(n%i==0)
           { 
              n/=i;                 
              current_term*=i;
              current_sum+=current_term;
            }

This can be simplified:

           std::uint_fast64_t current_sum=1;
           while(x%i==0)
           {
              x/=i;
              current_sum=current_sum*i+1;
           }

---

The first big step to improving the algorithm would be to exploit the fact that up to 500 test cases are passed at a time. If you read them all and find the largest, you can do a variant of Eratosthenes' sieve once to set up an array which allows you to factor all numbers up to that largest one very fast.

If that's not enough, it's probably necessary to switch factorisation approach, starting with Pollard's rho algorithm.