Project Euler Problem 5: Solution

solution.zig

// 2520 is the smallest number that can be divided by each of
// the numbers from 1 to 10 without any remainder.
//
// What is the smallest positive number that is evenly
// divisible by all of the numbers from 1 to 20?

const std = @import("std");
const assert = std.debug.assert;

const FactorMap = std.hash_map.AutoHashMap(u32, u32);

pub fn main() !void {
    const allocator = std.debug.global_allocator;
    var factor_counts = FactorMap.init(allocator);
    defer factor_counts.deinit();
    var required_factors = FactorMap.init(allocator);
    defer required_factors.deinit();

    var i: u32 = 2;
    while (i <= 20) : (i += 1) {
        factor_counts.clear();
        try factors(i, &factor_counts);
        var iter = factor_counts.iterator();
        while (iter.next()) |next| {
            var required = try required_factors.getOrPutValue(next.key, 0);
            if (required.value < next.value) required.value = next.value;
        }
    }

    var product: u32 = 1;
    var requirements = required_factors.iterator();
    while (requirements.next()) |next| {
        product *= try std.math.powi(u32, next.key, next.value);
    }

    var stdout = try std.io.getStdOut();
    const out = &stdout.outStream().stream;
    try out.print("{}\n", product);
    assert(product == 232792560);
}

fn factors(n_in: u32, factor_counts: *FactorMap) !void {
    var n = n_in;
    var f: u32 = 2;
    while (n > 1) {
        if (n % f == 0) {
            var entry = try factor_counts.getOrPutValue(f, 0);
            entry.value += 1;
            n /= f;
            f = 2;
        } else if (f == 2) {
            f += 1;
        } else {
            f += 2;
        }
    }
}

// Tests
const expect = std.testing.expect;
const expectEqual = std.testing.expectEqual;

fn expectFactors(num: u32, map: ...) void {
    const allocator = std.debug.global_allocator;
    var factor_counts = FactorMap.init(allocator);
    defer factor_counts.deinit();

    factors(num, &factor_counts) catch expect(false);

    expectEqual(map.len, factor_counts.count());
    comptime var arg = 0;
    inline while (arg < map.len) : (arg += 1) {
        const kv: [2]u32 = map[arg];
        if (factor_counts.get(kv[0])) |entry| {
            expectEqual(kv[1], entry.value);
        } else {
            expect(false);
        }
    }
}

test "factors" {
    expectFactors(2, []u32{2, 1});
    expectFactors(4, []u32{2, 2});
    expectFactors(20, []u32{2, 2}, []u32{5, 1});
}