549
URAL 1356 哥德巴赫猜想
題意：給出一個數，把它分解成幾個素數相加的形式，要求分解出的素數的數量最小。
這題分情況討論就可以了，首先需要知道哥德巴赫猜想即一個大於4的偶數可以分解成兩個素數和的形式。其次需要知道奇數加奇數等於偶數，奇數減奇數等於偶數。
那麼首先判斷n是否是素數，如果是直接輸出n就可以。
接下來判斷如果n是奇數，那麼先判斷n-2是否是素數，如果是的話那麼最小數量的素數和即n-2 與 2，如果不是那麼肯定能減一個奇素數數得到一個偶數再分解成兩個素數。這個奇素數首選肯定是3，因為3最小適合絕大多數情況。
如果n是偶數，那麼直接分解成兩個素數即可。
分解偶數直接枚舉素數暴力就可以了。這裏數據弱了，n不大於maxn可行，不然還是得一個一個枚舉。
#include <iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<map>
#include<set>
using namespace std;
#define maxn 100010
bool isprime[maxn];
int prime[maxn],nprime;
void getprime()
{
memset(isprime,1,sizeof(prime));
long long i,j;
nprime=0;
for(i=2; i<maxn; i++)
if(isprime[i])
{
prime[nprime++]=i;
for(j=i*i; j<maxn; j+=i)isprime[j]=0;
}
}
bool judgeprime(int n)
{
if(n<maxn)return isprime[n];
int l=(int)sqrt(n*1.0);
for(int i=0; prime[i]<=l; i++)
if(n%prime[i]==0)return 0;
return 1;
}
void divideeven(int n,int &x,int &y)
{
for(int i=1; prime[i]<n; i++)
if(judgeprime(n-prime[i]))
{
x=prime[i],y=n-x;
return;
}
}
int main()
{
int t,n,x,y;
getprime();
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
if(judgeprime(n))
{
printf("%d\n",n);
continue;
}
if(n&1)
{
if(judgeprime(n-2))printf("2 %d\n",n-2);
else divideeven(n-3,x,y),printf("3 %d %d\n",x,y);
}
else divideeven(n,x,y),printf("%d %d\n",x,y);
}
return 0;
}
最後更新：2017-04-03 14:54:20