Uva 10168 Summation of Four Primes 素数

[cpp] 
/*
*   Status: 10540903    10168   Summation of Four Primes    Accepted    C++ 0.864   2012-08-30 02:49:48
*   url:  http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1109
*   Time: 2012.8.30 10:30 around
*   Stratege: 通过打表，发现奇数是2，3开始的，偶数是2，2开始的，所以只要一层循环，就可以了
*
*/ 
#include <iostream> 
#include <cstdio> 
#include <cmath> 
#include <algorithm> 
#include <cstring> 
#include <queue> 
using namespace std ; 
 
#define LL long long 
#define MAXN  10000000 
int p[MAXN], prilen ; 
bool NotPrime[MAXN] ; 
int n ; 
 
void getPrime () 
{ 
    int i, j ; 
    for (i = 4; i < MAXN; i += 2) 
        NotPrime[i] = true ; 
    NotPrime[0] = NotPrime[1] = true ; 
    prilen = 1 ; 
    p[0] = 2 ; 
    for (i = 3; i < MAXN; i += 2) 
    { 
        if (!NotPrime[i]) 
        { 
            p[prilen++] = i ; 
            for (j = 2*i; j < MAXN; j += i) 
                NotPrime[j] = true ; 
        } 
    } 
} 
 
int main () 
{ 
    getPrime () ; 
    int i ; 
    while (scanf ("%d", &n) != EOF) 
    { 
        if (n < 8) 
        { 
            printf ("Impossible./n") ; 
            continue ; 
        } 
        if (n % 2 == 0) 
        { 
            printf ("2 2 ") ; 
            n -= 4 ; 
            for (i = 0; i < prilen; i ++) 
            { 
                if (!NotPrime[p[i]] && !NotPrime[n-p[i]]) 
                { 
                    printf ("%d %d/n", p[i], n-p[i]) ; 
                    break ; 
                } 
            } 
        } 
        else if (n % 2) 
        { 
            printf ("2 3 ") ; 
            n -= 5 ; 
            for (i = 0; i < prilen; i ++) 
            { 
                if (!NotPrime[p[i]] && !NotPrime[n-p[i]]) 
                { 
                    printf ("%d %d/n", p[i], n-p[i]) ; 
                    break ; 
                } 
            } 
        } 
    } 
    return 0 ; 
} 
//打表代码 
/*
int main ()
{
    getPrime () ;
    int i, j, k, l, q ;
    for (i = 100; i < 200; i ++)
    {
        for (j = 0; p[j] < i; j ++)
            for (k = 0; p[k] < i; k ++)
                for (q = 0; q < i; q ++)
                {
                    if (!NotPrime[i-p[j]-p[k]-p[q]] && i-p[j]-p[k]-p[q] >= 2)
                    {
                        cout << i << " " << p[j] << " " << p[k] << " " << p[q] << " " << i-p[j]-p
                            [k]-p[q] << endl ; 
                        goto L ;
                    }
                }
        cout << i << " " << "impossible" << endl ;
L:      continue ;
    }
    cin >> q; 
    return 0 ;
}
*/