UVa 10311 - Goldbach and Euler

题目：给你一个整数n，问能否拆成两个素数，如果可以给出差值最小的一组。

分析：数论。打表计算素数，然后二分判断，这里分成就两种情况讨论；

            如果n是奇数在其中必有一个数字是2，判断n-2是不是素数即可；

            如果n是偶数从（n-1）/2开始向左边枚举即可。

说明：注意这里1不算作素数╮(╯▽╰)╭。

#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>

using namespace std;

char visit[100000001];  
int  prime[10000001];

int bs(int r, int key)
{
	int mid,l = 0;
	while (l < r) {
		mid = (l+r+1)/2;
		if (prime[mid] >= key)
			r = mid-1;
		else l = mid;
	}
    return l;
}

int main()
{
 	memset(visit, 0, sizeof(visit));
    int count = 0;
    //prime[count ++] = 1;
    for (int i = 2; i < 100000001; ++ i) {    
        if (!visit[i])   
            prime[count ++] = i;  
        for (int j = 0; j < count && i*prime[j] < 100000001; ++ j) {  
            visit[i*prime[j]] = 1;  
            if (i%prime[j] == 0) break;  
        }  
    }prime[count] = 100000001;
    
    int n;
    while (~scanf("%d",&n)) {
		if (n < 5)
			printf("%d is not the sum of two primes!\n",n);
		else if (n%2) {
			if (prime[bs(count, n-2)+1] == n-2) 
				printf("%d is the sum of %d and %d.\n",n,2,n-2);
			else printf("%d is not the sum of two primes!\n",n);
		}else {
			int flag = 1;
			for (int i = bs(count, n/2); i >= 0; -- i) 
				if (prime[bs(count, n-prime[i])+1] == n-prime[i]) {
					printf("%d is the sum of %d and %d.\n",n,prime[i],n-prime[i]);
					flag = 0;
					break;
				}
			if (flag) printf("%d is not the sum of two primes!\n",n);
		}
	}
	
    return 0;
}

UVa 10311 - Goldbach and Euler

原文：http://blog.csdn.net/mobius_strip/article/details/44625817