Problem 9: Sum of divisors

Points

Small Case: 5 Answer: 1355

Large Case: 15 Answer: 4001488450455

Consider the number 4. It's divisors are 1,2 and 4. The sum of it's divisors is 7.

Now all numbers less than or equal to 7 can be respresented as a sum of distinct divisors of 4.

1 = 1
2 = 2.
3 = 1 + 2
4 = 4
5 = 1 + 4
6 = 2 + 4
7 = 1 + 2 + 4.

For 10, the divisors are 1,2,5 and 10 and the sum of it's divisors is 18. But 14 cannot be represented as a sum of distinct divisors of 10.

Find the sum of all numbers M less than or equal to N such that every number less than or equal to sum of it's divisors can be represented as a sum of distinct divisors of M.

Small Case: N=100
Large Case: N=10000000

Solution:

Practical Numbers are those numbers n such that every k <= sigma(n) is a sum of distinct divisors of n.It is also defined by as:
A number n = p1e1*p2e2*....*pkek with n>1 and primes p1<p2<...<pk is practical if and only if p1 = 2 and for every i from 2 to k

Reference:N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995[A005153]

Code:

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <iostream>
using namespace std;
#include<vector>
#include <math.h>
 
int primes[100000];
int ctr=0;
 
void sieve(int N)
{
     int M=(N-1)/2;
     int x=(floor(sqrt(N))-1)/2,i,j;
     vector<bool> S(M+1,0);
     primes[ctr++]=2;
     for (i=1;i<=x;i++)
         if (!S[i])
            for (j=2*i*(i+1);j<=M;j+=(2*i+1))
                S[j]=1;
 
     for (i=1;i<=M;i++)
         if (!S[i])
            primes[ctr++]=(2*i+1);
 
}
 
bool ispractical(int n)
{
    if (n%2==1)
            return 0;
    int c=0,j=n;
    long long sigma=1;
    while (j>1 && primes[c]*primes[c]<=n)
    {
        if (j%primes[c]==0)
        {
            int k=primes[c];                        
            if (k>sigma+1)
                    return 0;
            int m=k;
            while (j%k==0)
            {
                    m*=k;
                    j/=k;
            }
            sigma=sigma*((m-1)/(k-1));
        }
        c++;
    }
    if (j!=1)
        if (j>sigma+1)
                return 0;
    return 1; 
}
 

int main()
{ 
 
    int i,c=0,m;
    sieve(10000);
	long long max=10000000;
    long long sum=1;
    for (i=2;i<=max;i+=2)
    {
        if(ispractical(i))
        {
           sum+=i;
        }
    }
    printf("%lld\n",sum);
    return 0;
}