sol1.c File Reference

Problem 21 solution More...

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

Include dependency graph for sol1.c:

Functions
unsigned long	sum_of_divisors (unsigned int N)
	function to return the sum of proper divisors of N
int	main (int argc, char **argv)
	Main function.

Detailed Description

Problem 21 solution

Author

Krishna Vedala

Function Documentation

main()

int main	(	int	argc,
		char **	argv
	)

Main function.

{
    unsigned long sum = 0;
    unsigned int MAX_N = 500;
    if (argc == 2)
        MAX_N = atoi(argv[1]);
 
    /*
     * We use an array of flags to check if a number at the index was:
     * not-processed = 0
     * is amicable = 1
     * not amicable = -1
     */
    char *flags = (char *)calloc(MAX_N, sizeof(char));
 
    clock_t start_time = clock();
    int i;
    /* there are no such numbers till 10. Lets search from there on */
    for (i = 10; i < MAX_N; i++)
    {
        if (flags[i] != 0)
            /* already processed, skip */
            continue;
 
        unsigned int b = sum_of_divisors(i);
        if (b >= MAX_N)
            flags[i] = -1;
        else if (flags[b] == -1)
            continue;
 
        unsigned int c = sum_of_divisors(b);
        if (c == i && b != i)
        {
            /* found amicable */
            flags[b] = 1;
            flags[i] = 1;
            sum += b + i;
#ifdef DEBUG
            printf("Amicable: %4d : %4d\n", i, b);
#endif
        }
        else
        {
            flags[i] = -1;
            if (b < MAX_N)
                flags[b] = -1;
        }
    }
 
    clock_t end_time = clock();
 
    printf("\nTime taken: %.4g millisecond\n",
           1e3 * (end_time - start_time) / CLOCKS_PER_SEC);
    printf("Sum of all numbers = %lu\n", sum);
 
    free(flags);
    return 0;
}

Here is the call graph for this function:

sum_of_divisors()

unsigned long sum_of_divisors

(

unsigned int

N

)

function to return the sum of proper divisors of N

{
    unsigned long sum = 1 + N; /* 1 and itself are always a divisor */
    /* divisors are symmertically distributed about the square-root */
    for (unsigned int i = 2; i * i < N; i++)
    {
        if ((N % i) != 0)
            /* i is not a divisor of N */
            continue;
 
        // #ifdef DEBUG
        //         printf("%4d, %4d,", i, N / i);
        // #endif
 
        sum += i + (N / i);
    }
    // #ifdef DEBUG
    //     printf("\nSum of divisors of %4d: %4d\n", N, sum);
    // #endif
    return sum;
}