Friday, June 7, 2013

[Project Euler] Problem 5 in C

Problem: Project Euler Problem 5

All we need to find was least common multiple for numbers 1 to 20.
We could have done it easily by hand but I wanted to develop an algorithm for this :)
Very simple program.

#include <stdio.h>
#include <stdlib.h>
#include <inttypes.h>
uint64_t gcd(uint64_t a, uint64_t b);
int main( )
{
    uint64_t initialFactor = 2, finalFactor = 20;
    uint64_t lcm = 1, i;

    for (i = initialFactor; i <= finalFactor; i++){
        lcm*= i / gcd(lcm, i);
    }
    printf("%llu\n",lcm);
    return 0;
}

//Euclidean greatest common divisor algorithm
uint64_t gcd(uint64_t a, uint64_t b){
    if (a == 0) return b;
    return gcd(b%a, a);
}


Answer:

No comments:

Post a Comment