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:
The part I don't understand is actually the final for loop.. everything else I understand perfectly!
Please help!
Thank you in advance!
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:
Rich (BB code):
#include <iostream>
using namespace std;
int const MAXN = 50010;
bool sieve[MAXN] = {false};
long a[MAXN];
long s[MAXN];
long cnt = 0;
int eratosthenes(long n)
{
for(long i = 2; i <= n; i++)
if(!sieve)
{
a[cnt] = i;
cnt++;
for(long j = i+i; j <= n; j+= i)
sieve[j] = true;
}
if (a[cnt-1] == n) return 1;
return 0;
}
int main()
{
long n;
cin >> n;
if (n == 1)
{
cout << 0 << endl;
return 0;
}
int is_n_prime;
is_n_prime = eratosthenes(n);
long p = n+1;
bool is_p_prime;
do
{
is_p_prime = true;
long i = 0;
while(is_p_prime && a*a <= p)
{
if (p%a == 0)
{
is_p_prime = false;
p++;
}
i++;
}
}while(!is_p_prime);
s[0] = 1;
for(long k = 0; k < cnt; k++)
{
long x = a[k];
for(long i = x; i <= n; i++)
s = (s+s[i-x])%p;
}
s[n] = (s[n]+p-is_n_prime)%p;
cout << s[n] << endl;
return 0;
}The part I don't understand is actually the final for loop.. everything else I understand perfectly!
Please help!
Thank you in advance!
