sol3.c File Reference

Problem 5 solution (Fastest). More...

#include <stdio.h>

Include dependency graph for sol3.c:

Functions
unsigned long	gcd (unsigned long a, unsigned long b)
	Compute Greatest Common Divisor (GCD) of two numbers using Euclids algorithm.
unsigned long	lcm (unsigned long a, unsigned long b)
	Compute Least Common Multiple (LCM) of two numbers.
int	main (void)
	Main function.

Detailed Description

Problem 5 solution (Fastest).

Solution is the LCM of all numbers between 1 and 20.

See also

Slowest: problem_5/sol1.c

Slower: problem_5/sol2.c

Function Documentation

gcd()

unsigned long gcd	(	unsigned long	a,
		unsigned long	b
	)

Compute Greatest Common Divisor (GCD) of two numbers using Euclids algorithm.

Parameters

a	first number
b	second number

Returns

GCD of a and b

{
    unsigned long r;
    if (a > b)
    {
        unsigned long t = a;
        a = b;
        b = t;
    }
    while ((r = (a % b)))
    {
        a = b;
        b = r;
    }
    return b;
}

lcm()

unsigned long lcm	(	unsigned long	a,
		unsigned long	b
	)

Compute Least Common Multiple (LCM) of two numbers.

Parameters

a	first number
b	second number

Returns

LCM of a and b

{
    unsigned long long p = (unsigned long long)a * b;
    return p / gcd(a, b);
}

Here is the call graph for this function:

main()

int main

(

void

)

Main function.

Returns

0 on exit

{
    unsigned long ans = 1;
    unsigned long i;
    for (i = 1; i <= 20; i++)
    {
        ans = lcm(ans, i);
    }
    printf("%lu\n", ans);
    return 0;
}

Here is the call graph for this function: