C Implementation of Problem 22
View source code here on GitHub!
Includes
<inttypes.h>
(implicitly, via utils.h)<stdint.h>
(implicitly, via utils.h)<stdlib.h>
(implicitly, via utils.h)<string.h>
(implicitly, via utils.h)<stdio.h>
(implicitly, via utils.h)<direct.h> (implicitly, via utils.h & if compiled for Windows)
<windows.h> (implicitly, via utils.h & if compiled for Windows)
<libgen.h> (implicitly, via utils.h & if not compiled for Windows)
<libgen.h> (implicitly, via utils.h & if not compiled for Windows)
Solution
-
int cmpstr(const void *a, const void *b)
A wrapper around
strcmp()
to adapt it forqsort()
-
uint64_t p0022()
-
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 22
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
10If we list all the natural numbers below 10 that are multiples of 3 or 5, we
11get 3, 5, 6 and 9. The sum of these multiples is 23.
12
13Find the sum of all the multiples of 3 or 5 below 1000.
14*/
15#ifndef EULER_P0022
16#define EULER_P0022
17#include <stdint.h>
18#include <inttypes.h>
19#include <stdio.h>
20#include "include/macros.h"
21#include "include/utils.h"
22
23int cmpstr(const void* a, const void* b) {
24 return strcmp(*(const char**)a, *(const char**)b);
25}
26
27uint64_t EMSCRIPTEN_KEEPALIVE p0022() {
28 uint64_t answer = 0;
29 char *fstring = get_data_file("p0022_names.txt");
30 const uint32_t name_count = 5163;
31 char *names[5163] = {};
32 size_t idx = 0, i = 0, pi = 0;
33 do {
34 while (fstring[i] && fstring[i] != ',')
35 i++;
36 const size_t len = i - pi - 2;
37 if (unlikely(len == 0))
38 continue;
39 names[idx] = (char *)malloc(len);
40 memcpy(names[idx], fstring + pi + 1, len);
41 names[idx++][len] = 0;
42 pi = ++i;
43 } while (fstring[i]);
44 qsort(names, sizeof(names)/sizeof(*names), sizeof(*names), cmpstr);
45 for (idx = 0; idx < name_count; idx++) {
46 uint64_t score = 0;
47 for (i = 0; names[idx][i]; i++)
48 score += names[idx][i] & 0x3F;
49 answer += score * (idx + 1);
50 }
51 return answer;
52}
53
54PROGRAM_TAIL("%" PRIu64, p0022)
55#endif