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!
    Please help! :)
    Thank you in advance!
     
Loading...