如果N為奇數(shù)，那么前兩個(gè)素?cái)?shù)為2和3；如果N為偶數(shù)，那么前兩個(gè)素?cái)?shù)為2和2。這樣一來轉(zhuǎn)化成了將一個(gè)偶數(shù)分解成兩個(gè)素?cái)?shù)的和。
以下是我的代碼：
#include <cstdio>
using namespace std;
const int kMaxn = 10000000;
int cnt, Prime[680000];
bool isNotPrime[ kMaxn + 7 ];
int n;
void GetPrime ()
{
cnt = 0;
for ( int i = 2; i <= kMaxn; i++ )
{
if ( !isNotPrime[i] )
Prime[++cnt] = i;
for ( int j = 1; j <= cnt && i * Prime[j] <= kMaxn; j++ )
{
isNotPrime[ i * Prime[j] ] = true;
if ( i % Prime[j] == 0 )
break;
}
}
}
void Goldbach ( int x )
{
for ( int i = 1; i <= cnt && Prime[i] <= x; i++ )
if ( !isNotPrime[ x - Prime[i] ] )
{
printf ( "%d %d\n", Prime[i], x-Prime[i] );
return;
}
}
void Solve ()
{
if ( n & 1 )
{
n -= 5;
if ( n < 4 )
{
printf ( "Impossible.\n" );
return;
}
printf ( "%d %d ", 2, 3 );
}
else
{
n -= 4;
if ( n < 4 )
{
printf ( "Impossible.\n" );
return;
}
printf ( "%d %d ", 2, 2 );
}
Goldbach ( n );
}
int main()
{
#ifndef ONLINE_JUDGE
freopen ( "data.in", "r", stdin );
#endif
GetPrime ();
//printf ( "%d\n", cnt );
while ( scanf ( "%d", &n ) == 1 )
Solve ();
return 0;
}
posted on 2011-09-06 23:30
lee1r 閱讀(583)
評論(0) 編輯 收藏 引用 所屬分類:
題目分類：數(shù)學(xué)/數(shù)論