C Implementation of Problem 12

View source code here on GitHub!

Note

While this is a complete solution, and will eventually complete, until prime_counter utilizes the prime sieve (as opposed to the current implementation that searches naively with a cache) it will be quite slow. That conversion is underway.

Includes

Solution

uint64_t p0012()
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 12
 3
 4
 5
 6Problem:
 7
 8The sequence of triangle numbers is generated by adding the natural numbers. So
 9the 7th triangle number would be 1 + 2 + 3 + 4 + 5 + 6 + 7 = 28. The first ten
10terms would be:
11
121, 3, 6, 10, 15, 21, 28, 36, 45, 55, ...
13
14Let us list the factors of the first seven triangle numbers:
15
16     1: 1
17     3: 1,3
18     6: 1,2,3,6
19    10: 1,2,5,10
20    15: 1,3,5,15
21    21: 1,3,7,21
22    28: 1,2,4,7,14,28
23
24We can see that 28 is the first triangle number to have over five divisors.
25
26What is the value of the first triangle number to have over five hundred
27divisors?
28*/
29#ifndef EULER_P0012
30#define EULER_P0012
31#include <stdint.h>
32#include <inttypes.h>
33#include <stdio.h>
34#include "include/macros.h"
35#include "include/factors.h"
36
37uint64_t EMSCRIPTEN_KEEPALIVE p0012() {
38    uint64_t current = 1;
39    uint32_t i = 2;
40    while (true) {
41        current += i;  // 3, 21, ...
42        ++i;
43        current += i;  // 6, 28, ...
44        if (proper_divisor_count(current) > 500)
45            return current;
46        ++i;
47        current += i;  // 10, 36, ...
48        if (proper_divisor_count(current) > 500)
49            return current;
50        ++i;
51        current += i;  // 15, 45, ...
52        ++i;
53    }
54    return -1;
55}
56
57PROGRAM_TAIL("%" PRIu64, p0012)
58#endif

Tags: c-iterator, divisor-count, divisibility, marked-slow