uva 10168 哥德巴赫猜想

系统管理员 2022-08-04 00:47 57阅读 0赞

这题看了题解才知道，巧妙地利用了哥德巴赫猜想，即任意一个大于4的偶数可以分解为两个质数的和的形式。

这题要分解成4个质数，显然如果n小于8的话是无法满足的。当n大于8的时候，应该凑成偶数的形式，

比如当n是奇数的时候，先分解为2和3，剩下的肯定是大于4的偶数，当n是偶数的时候，先分解成2和2，

剩下的两个质数暴力枚举它之间的质数看哪两个相加等于剩余的和就行。

#include<bitset>
    #include<map>
    #include<vector>
    #include<cstdio>
    #include<iostream>
    #include<cstring>
    #include<string>
    #include<algorithm>
    #include<cmath>
    #include<stack>
    #include<queue>
    #include<set>
    #define inf 0x3f3f3f3f
    #define mem(a,x) memset(a,x,sizeof(a))
    
    using namespace std;
    
    typedef long long ll;
    typedef pair<int,int> pii;
    
    inline int in()
    {
        int res=0;
        char c;
        while((c=getchar())<'0' || c>'9');
        while(c>='0' && c<='9')res=res*10+c-'0',c=getchar();
        return res;
    }
    
    const int N=10000001;
    bitset <N>vis;
    //bool vis[N];
    int prime[2000000];
    int main()
    {
        int p=0;
        for(int i=2;i<N;i++)
        {
            if(!vis[i])
            {
                prime[p++]=i;
                for(int j=i+i;j<N;j+=i)
                {
                    vis[j]=1;
                }
            }
        }
        int n;
        while(~scanf("%d",&n))
        {
            if(n<8)
            {
                puts("Impossible.");
                continue;
            }
            if(n & 1)
            {
                for(int i=0;i<p;i++)
                {
                    if(!vis[n-5-prime[i]])
                    {
                        printf("2 3 %d %d\n",prime[i],n-5-prime[i]);
                        break;
                    }
                }
            }
            else
            {
                for(int i=0;i<p;i++)
                {
                    if(!vis[n-4-prime[i]])
                    {
                        printf("2 2 %d %d\n",prime[i],n-4-prime[i]);
                        break;
                    }
                }
            }
        }
        return 0;
    }