Thread: Find abundant numbers from 1 to 1.0e7

The problem is to find (not store) abundant numbers from 1 to 10mil in less than 10s cpu time, but we need a lower complexity algorithm. My code execution time is 18 sec. Keep in mind that the limitation are not to use some sort of function that needs math.h nor a dynamic or static data structure. Please help...!

Code:

#include <stdio.h>
#define MAXNUM 1.0e7

int main()
{

  int n, i, no_ab, sum_div, div, sum_ab, flag_ab, last, flag_pr;

  /*
     n : is counters for loop
     no_ab : sum of no abundunt numbers from 1 to MAXNUM
     sum_ab : sum of abundunt numbers from 1 to MAXNUM
     sum_div : sum of divisors for current n
     div : every possible number that can be divisor
     flag_ab : if the flag_ab == 1 ,the number(n) is abundant
   */

  sum_ab = 0;
  no_ab = 0;

  for (n = 1; n <= MAXNUM; n++) {

    flag_pr = 0;
    last = n % 10;

    if ((last == 1 || last == 3 || last == 7 || last == 9) && n % 21 != 0) {
      flag_pr = 1;
    }                           // this is a trick ,to exclude some     prime numbers 

    // 21 is GCD of abundunt numbers in [1, 1.0e7] with last digit 1 or 3 or 7 or 9

    if ((n % 2 == 0 || n % 3 == 0) && flag_pr == 0) { // The smallest abundant number not divisible by 2 or by 3 is 5391411025 

      sum_div = 1;              // 1 is a divisor of any integer, so we include it
      flag_ab = 0;              // reset flag_ab

      for (div = 2; (div * div) < n; div++) { // this loop finds divisors of current n
        if (n % div == 0) {     // cheak if the division is perfect
          sum_div += div + (n / div); // then include this divisor and its symmetric
          if (sum_div > n) {    // break from the loop once you have proved that the number is 'abundant'
            sum_ab++;
            flag_ab = 1;
            break;
          }
        }
      }
      if (div * div == n) {     // cheak if divisor is square root of n
        sum_div += div;         // then include this divisor
        if (sum_div > n & flag_ab == 0) { // cheak if now is abundunt
          sum_ab++;
          flag_ab = 1;
        }
      }
    }
  }
  printf("Abundunt = %d\n", sum_ab);
}

Since you're only checking numbers that are divisible by 2 or 3, here is a simple way to speed it up a little.

Code:

#include <stdio.h>
 
#define MAXNUM 10000000
 
int main() {
    int count_ab = 0;
 
    // Process numbers divisible by 2
    for (int n = 12; n <= MAXNUM; n += 2) {
        int sum_div = 1, div = 2;
        for ( ; div * div < n; div++) {
            if (n % div == 0) {
                sum_div += div + n / div;
                if (sum_div > n) {
                    count_ab++;
                    break;
                }
            }
        }
        if (sum_div <= n && div * div == n && sum_div + div > n)
            count_ab++;
    }
 
    // Process numbers divisible by 3 but not by 2
    for (int n = 15; n <= MAXNUM; n += 6) {
        // 21 is a divisor of abundunt numbers in [1, 1.0e7] with last digit 1 or 3 or 7 or 9
        if (n % 10 != 5 && n % 21 != 0) continue;
        int sum_div = 1, div = 3; // not divisible by even numbers
        for ( ; div * div < n; div += 2) {
            if (n % div == 0) {
                sum_div += div + n / div;
                if (sum_div > n) {
                    count_ab++;
                    break;
                }
            }
        }
        if (sum_div <= n && div * div == n && sum_div + div > n)
            count_ab++;
    }
 
    printf("Abundunt = %d\n", count_ab);
    return 0;
}

You say you can't use a "data structure", but if you can use an array then this is a good ten times faster.

Code:

#include <stdio.h>
 
#define MAXNUM 10000000
 
int xp[MAXNUM + 1];
 
int main() {
    for (int i = 2; i <= MAXNUM; ++i)
        for (int j = i * 2; j <= MAXNUM; j += i)
            xp[j] += i;
 
    int count = 0;
    for (int i = 2; i <= MAXNUM; ++i)
        if (xp[i] > i)
            ++count;
 
    printf("%d\n", count);
 
    return 0;
}