-
-
Notifications
You must be signed in to change notification settings - Fork 4.4k
/
sol2.c
59 lines (55 loc) · 1.37 KB
/
sol2.c
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
/**
* \file
* \brief [Problem 5](https://projecteuler.net/problem=5) solution - Naive
* algorithm (Improved over problem_5/sol1.c)
* @details Little bit improved version of the naive `problem_5/sol1.c`. Since
* the number has to be divisable by 20, we can start at 20 and go in 20 steps.
* Also we don't have to check against any number, since most of them are
* implied by other divisions (i.e. if a number is divisable by 20, it's also
* divisable by 2, 5, and 10). This all gives a 97% perfomance increase on my
* machine (9.562 vs 0.257)
*
* \see Slower: problem_5/sol1.c
* \see Faster: problem_5/sol3.c
*/
#include <stdio.h>
#include <stdlib.h>
/**
* @brief Hack to store divisors between 1 & 20
*/
static unsigned int divisors[] = {
11, 13, 14, 16, 17, 18, 19, 20,
};
/** Checks if a given number is devisable by every number between 1 and 20
* @param n number to check
* @returns 0 if not divisible
* @returns 1 if divisible
*/
static int check_number(unsigned long long n)
{
for (size_t i = 0; i < 7; ++i)
{
if (n % divisors[i] != 0)
{
return 0;
}
}
return 1;
}
/**
* @brief Main function
*
* @return 0 on exit
*/
int main(void)
{
for (unsigned long long n = 20;; n += 20)
{
if (check_number(n))
{
printf("Result: %llu\n", n);
break;
}
}
return 0;
}