数论刷题-uva【10168】- Summation of Four Primes

96 阅读 0 评论 64 点赞

我是靠谱客的博主要减肥服饰，最近开发中收集的这篇文章主要介绍数论刷题-uva【10168】- Summation of Four Primes，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

Euler proved in one of his classic theorems that prime numbers are infinite in number. But can every
number be expressed as a summation of four positive primes? I don’t know the answer. May be you
can help!!! I want your solution to be very efficient as I have a 386 machine at home. But the time limit
specified above is for a Pentium III 800 machine. The definition of prime number for this problem is
“A prime number is a positive number which has exactly two distinct integer factors”. As for example
37 is prime as it has exactly two distinct integer factors 37 and 1.

Input

The input contains one integer number N (N ≤ 10000000) in every line. This is the number you will
have to express as a summation of four primes. Input is terminated by end of file.

Output

For each line of input there is one line of output, which contains four prime numbers according to
the given condition. If the number cannot be expressed as a summation of four prime numbers print
the line ‘Impossible.’ in a single line. There can be multiple solutions. Any good solution will be
accepted.

Sample Input
24
36
46

Sample Output
3 11 3 7
3 7 13 13
11 11 17 7

题解：给你一个数，判断能不能分成四个素数的和，我们知道最小的素数是2，那么就可以确定小于8的数是不能够分成的，那么当数大于等于8时候，如果为奇数我们分出两个2,3变为偶数，如果为偶数，可以分出2,2，剩下的数为大于2的偶数，根据哥德巴赫猜想，一定有解。

#include <bits/stdc++.h>

using namespace std;

const int Max = 11000000;

bool vis[Max];

void Getprime()
{
    for(int i = 2;i<Max;i++)
    {
        if(!vis[i])
        {
            for(int j = i+i;j<Max;j+=i)
            {
                vis[j]  = true;
            }
        }
    }
}

int main()
{
    int n;

    Getprime();

    while(~scanf("%d",&n))
    {
        if(n<8)
        {
            printf("Impossible.n");
        }
        else 
        {
            if(n%2 == 0)
            {
                printf("2 2");

                n-=4;
            }
            else 
            {
                n-=5;
                printf("2 3");
            }

            for(int i = 2;i+i<=n;i++)
            {
                if(!vis[i] && !vis[n-i])
                {
                    printf(" %d %dn",i,n-i);
                    break;
                }

            }

        }
    }
    return 0;
}