Last active
March 28, 2016 02:02
-
-
Save meylingtaing/0e155eb6d9974fc99a03 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <stdio.h> | |
#include <math.h> | |
#include <stdlib.h> | |
#define MAX 28123 | |
int get_divisors(int, int **); | |
int main(void) { | |
int *divisors; | |
int n, i; | |
int abundant_nums[MAX] = {0}; | |
int abundant_nums_count = 0; | |
// Get abundant numbers | |
for (n = 1; n < MAX; n++) { | |
int sum = 0; | |
// Get sum of divisors | |
int num_divisors = get_divisors(n, &divisors); | |
for (i = 0; i < num_divisors; i++) { | |
sum += divisors[i]; | |
} | |
free(divisors); | |
if (sum > n) { | |
abundant_nums[abundant_nums_count++] = n; | |
} | |
} | |
// Make an array for the possible values | |
int all_sums[MAX + 1]; | |
for (i = 0; i < MAX + 1; i++) | |
all_sums[i] = 1; | |
// Remove all the bad values | |
int add_a; | |
int add_b; | |
for (add_a = 0; add_a < abundant_nums_count; add_a++) { | |
for (add_b = add_a; add_b < abundant_nums_count; add_b++) { | |
int sum = abundant_nums[add_a] + abundant_nums[add_b]; | |
if (sum < MAX + 1) | |
all_sums[sum] = 0; | |
} | |
} | |
// Now find the total | |
long int solution = 0; | |
for (i = 0; i < MAX + 1; i++) { | |
if (all_sums[i]) | |
solution += i; | |
} | |
printf("Solution: %ld\n", solution); | |
return 0; | |
} | |
/* get_divisors: Need to pass in a pointer to an array of integers */ | |
int get_divisors(int n, int **result_ptr) { | |
int num_divisors = 0; | |
// Just picking a large number | |
int *result = malloc(sizeof(int) * 1000); | |
// 1 is always in the result | |
result[num_divisors++] = 1; | |
// Proper divisors only | |
/* | |
if (n != 1) { | |
result[num_divisors++] = n; | |
} | |
//*/ | |
int max = floor(sqrt(n)); | |
int divisor = 2; | |
while (divisor <= max) { | |
if (n % divisor == 0) { | |
result[num_divisors++] = divisor; | |
int other_divisor = n / divisor; | |
if (other_divisor > divisor) | |
result[num_divisors++] = other_divisor; | |
} | |
divisor++; | |
} | |
*result_ptr = result; | |
// Return number of divisors | |
return num_divisors; | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment