如果N为奇数，那么前两个素数为2和3；如果N为偶数，那么前两个素数为2和2。这样一来转化成了将一个偶数分解成两个素数的和。
以下是我的代码：
#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 阅读(547)
评论(0) 编辑 收藏 引用 所属分类:
题目分类：数学/数论