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);
}