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.
1/*
2Project Euler Problem 5
3
4Problem:
5
62520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder.
7
8What is the smallest positive number that is evenly divisible by all of the numbers from 1 to 20?
9*/
10#ifndef EULER_P0005
11#define EULER_P0005
12#include <stdint.h>
13#include <iostream>
14#include "include/macros.hpp"
15#include "include/primes.hpp"
16
17uint32_t EMSCRIPTEN_KEEPALIVE p0005() {
18 uint32_t answer = 1;
19 uint8_t factor_tracker[20] = {0}, local_factor_tracker[20] = {0};
20 for (uint8_t i = 2; i < 21; i++) {
21 PrimeFactors<uint8_t> pfc = prime_factors<uint8_t>(i);
22 while (pfc.has_next())
23 local_factor_tracker[pfc.next()]++;
24 for (uint8_t i = 2; i < 20; i++) {
25 factor_tracker[i] = std::max(factor_tracker[i], local_factor_tracker[i]);
26 local_factor_tracker[i] = 0;
27 }
28 }
29 for (uint8_t i = 2; i < 20; i++)
30 for (uint8_t j = 0; j < factor_tracker[i]; j++)
31 answer *= i;
32 return answer;
33}
34
35PROGRAM_TAIL(p0005)
36#endif