Problem 5 — Smallest Multiple

Problem Analysis

A number "evenly divisible by all of the numbers from 1 to N" is exactly the least common multiple of the set {1, 2, ..., N}: the smallest positive integer that has every member of the set as a divisor. So the smallest positive number divisible by all of 1..N is precisely the least common multiple of 1..N, and by definition nothing smaller can work.

The tool that makes this tractable is the identity lcm(a, b) = a × b / gcd(a, b), in which the greatest common divisor is the largest integer dividing both a and b. This identity lets me build the least common multiple of a whole set as a sequence of pairwise combinations, threading a running accumulator through the range. Each pairwise step needs only one greatest common divisor, which the Euclidean algorithm computes in O(log(min(a, b))) steps, so the overall cost is O(N log N) bit operations - negligible here.

One subtlety matters for scale. By the prime factorisation view, the least common multiple of 1..N is the product, over every prime p up to N, of the highest prime power of p not exceeding N, so the result grows rapidly. For N = 20 it fits in 32 bits, but for the extra cases (N up to 100) it reaches 40+ decimal digits, far beyond any native integer type - so I need arbitrary-precision arithmetic.

Solution Approach

Iterative least common multiple via the greatest common divisor (Python and C, index 0)

Both files implement the same algorithm: start with a running result of 1 (the identity element for the least common multiple), then for each y from 2 to N replace result with the least common multiple of result and y. After the loop, result equals the least common multiple of 1..N.

In the Python solution the entire computation is a single functools.reduce over range(2, n + 1) with initial accumulator 1 and the lambda x * y // math.gcd(x, y) - a direct transcription of the identity. I rely on Python's built-in arbitrary-precision integers, so multiplying and floor-dividing huge numbers just works with no special handling. I chose math.gcd over a hand-written loop because the standard-library greatest common divisor is implemented in C and is faster. I also write x * y // gcd (multiply first, then divide) rather than x // gcd * y; both are exact because the greatest common divisor divides x, but the chosen form mirrors the textbook identity directly.

In the C solution I have no native big integer, so I implemented a minimal BigInt: an array of 32-bit limbs in little-endian order (least-significant limb first), base 2^32. Three primitives drive everything:

• bi_div_small divides the BigInt by a small value and returns the remainder, walking limbs from most significant to least and carrying the remainder forward in a 64-bit intermediate ((rem << 32) | limb).
• bi_mul_small multiplies the BigInt by a small value, walking limbs from least to most significant and propagating carry - which is why little-endian order is convenient.
• bi_lcm_small computes the least common multiple of result and y in place: it copies result, reduces the copy modulo y with bi_div_small to get a small remainder, finds the greatest common divisor of that remainder and y with the native gcd_ll, then divides result by that greatest common divisor and multiplies by y.

The crucial design choice in C is that I never implement a big-integer greatest common divisor. Because gcd(a, b) = gcd(a mod b, b) and y is small, one modular reduction step turns the big operand into a small one, after which the whole greatest common divisor runs in native long long arithmetic. Finally bi_to_str converts the result to decimal by repeated division by 10, collecting digits least-significant-first into a stack buffer and reversing them into a heap-allocated string.