-
Notifications
You must be signed in to change notification settings - Fork 0
/
day 71
66 lines (57 loc) · 1.38 KB
/
day 71
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
60
61
62
63
64
65
66
#include <iostream>
#include <vector>
int main()
{
const unsigned int MaxNumber = 1000;
// store number of ways to represent a number as a sum of primes
std::vector<unsigned long long> combinations(MaxNumber + 1, 0);
// degenerated case
combinations[0] = 1;
// store all primes
std::vector<unsigned int> primes;
for (unsigned int i = 2; i <= MaxNumber; i++)
{
bool isPrime = true;
// test against all prime numbers we have so far (in ascending order)
for (auto p : primes)
{
// next prime is too large to be a divisor ?
if (p*p > i)
break;
// divisible ? => not prime
if (i % p == 0)
{
isPrime = false;
break;
}
}
// only primes after this point ...
if (!isPrime)
continue;
primes.push_back(i);
// now add all solutions
for (unsigned int pos = 0; pos <= MaxNumber - i; pos++)
combinations[pos + i] += combinations[pos];
}
//#define ORIGINAL
#ifdef ORIGINAL
// find first number with more than 5000 combinations
for (size_t i = 0; i < combinations.size(); i++)
if (combinations[i] > 5000)
{
std::cout << i << std::endl;
break;
}
#else
unsigned int tests = 1;
std::cin >> tests;
while (tests--)
{
// look up combinations
unsigned int n;
std::cin >> n;
std::cout << combinations[n] << std::endl;
}
#endif
return 0;
}