C Implementation of Problem 5

View source code here on GitHub!

Includes

Solution

uint32_t p0005()
int main(int argc, char const *argv[])

Note

This function is only present in the Python test runner, or when compiling as a standalone program. It is not present when compiling for the Unity test runner.

 1/*
 2Project Euler Problem 5
 3
 4I know that this could be done faster with a traditional for loop, but I wanted
 5to see if iterators were reasonably possible in C, since it makes the prime
 6number infrastructure a lot easier to set up.
 7
 8Problem:
 9
102520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder.
11
12What is the smallest positive number that is evenly divisible by all of the numbers from 1 to 20?
13*/
14#ifndef EULER_P0005
15#define EULER_P0005
16#include <stdint.h>
17#include <inttypes.h>
18#include <stdio.h>
19#include "include/macros.h"
20#include "include/primes.h"
21
22uint32_t EMSCRIPTEN_KEEPALIVE p0005() {
23    uint32_t answer = 1;
24    uint8_t factor_tracker[20] = {0}, local_factor_tracker[20] = {0};
25    prime_factor_counter pfc;
26    for (uint8_t i = 2; i < 21; i++) {
27        pfc = prime_factors(i);
28        while (!pfc.exhausted)
29            local_factor_tracker[next(pfc)]++;
30        for (uint8_t i = 2; i < 20; i++) {
31            factor_tracker[i] = max(factor_tracker[i], local_factor_tracker[i]);
32            local_factor_tracker[i] = 0;
33        }
34        free_prime_factor_counter(pfc);
35    }
36    for (uint8_t i = 2; i < 20; i++)
37        for (uint8_t j = 0; j < factor_tracker[i]; j++)
38            answer *= i;
39    return answer;
40}
41
42PROGRAM_TAIL("%" PRIu32, p0005)
43#endif

Tags: c-iterator, divisibility, factorization, prime-number