This is my method:
1. Use a sieve to produce all the 78k+ primes upto 1M. This takes just a split second.
2. Calculate the array pairs[1M+1], where pairs[n] is the number of ways n can be the sum of two different primes. I use the obvious O(N^2) for this by double looping through all primes and incrementing pairs[prime1+prime2]. This, however takes way too long (roughly 78k*78k/2 = 3G iterations).
3. Recursively fill the array ways[1M+1], where ways[n] is the number of ways the amount n can be paid: ways[1]=0; ways=ways[i-1]+pairs. This step also takes a split second.
Can someone push me into the right direction?
) This works in time linear in the number of primes.
