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