# A problem

Discussion in 'Programmer's Corner' started by Vexorian, Jan 30, 2010.

1. ### Vexorian Thread Starter New Member

Jan 30, 2010
1
0
Hello,
I have been assigned to solve a problem with C++. The problem states:
The user inputs a number n. Then the number of sums of prime numbers, which are all equal to n, must be stored in S. For example S(9) = 4, because 9 = 3 + 3 + 3; 9 = 2 + 2 + 2 + 3; 9 = 2 + 7; 9 = 2 + 2 + 5. Finally we have a number p, which is the first prime number, greater than n. In this case, p = 11. The remainder of S / n must be found. 2 <= n <= 50000.

EXAMPLE:

Input
9
Output
4

The problem is, that I can't make an efficient algorithm for finding S... I made an algorithm but it's extremely slow for numbers over 500. This is the solution made by another person.. but I cannot understand how it works:
Code ( (Unknown Language)):
1. #include <iostream>
2.
3. using namespace std;
4.
5. int const MAXN = 50010;
6.
7. bool sieve[MAXN] = {false};
8. long a[MAXN];
9. long s[MAXN];
10. long cnt = 0;
11.
12. int eratosthenes(long n)
13. {
14.     for(long i = 2; i <= n; i++)
15.         if(!sieve[i])
16.         {
17.             a[cnt] = i;
18.             cnt++;
19.             for(long j = i+i; j <= n; j+= i)
20.             sieve[j] = true;
21.         }
22.     if (a[cnt-1] == n) return 1;
23.     return 0;
24. }
25.
26. int main()
27. {
28.         long n;
29.     cin >> n;
30.     if (n == 1)
31.     {
32.         cout << 0 << endl;
33.         return 0;
34.     }
35.
36.     int is_n_prime;
37.     is_n_prime = eratosthenes(n);
38.     long p = n+1;
39.     bool is_p_prime;
40.     do
41.         {
42.         is_p_prime = true;
43.         long i = 0;
44.         while(is_p_prime && a[i]*a[i] <= p)
45.             {
46.          if (p%a[i] == 0)
47.              {
48.             is_p_prime = false;
49.             p++;
50.          }
51.         i++;
52.         }
53.     }while(!is_p_prime);
54.
55.     s[0] = 1;
56.     for(long k = 0; k < cnt; k++)
57.        {
58.         long x = a[k];
59.         for(long i = x; i <= n; i++)
60.             s[i] = (s[i]+s[i-x])%p;
61.         }
62.
63.     s[n] = (s[n]+p-is_n_prime)%p;
64.     cout << s[n] << endl;
65.
66.    return 0;
67. }[/i][/i][/i][/i][/i][/i]

The part I don't understand is actually the final for loop.. everything else I understand perfectly!