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