首页 > 代码库 > UVa 10948 - The primary problem

UVa 10948 - The primary problem

题目:给你一个数n,找到两个素数使得这两素数的和为n,且插值最大。

分析:数论、贪心。

            首先,利用筛法求出前1000000内的素数;

            然后,按顺序查询,第一组找到的即为解。

说明:目标前1000

#include <iostream>
#include <cstdlib>
#include <cstdio>

using namespace std;

int visit[1000000] = {0};
int prime[1000000] = {0};

int main()
{
	int count = 0;
	visit[0] = visit[1] = 1;
	for (int i = 2 ; i < 1000000 ; ++ i )
		if (!visit[i]) {
			prime[count ++] = i;
			for (int j = i<<1 ; j < 1000000 ; j += i)
				visit[j] = 1;
		}
	int n;
	while (cin >> n && n) {
		int flag = 0;
		for (int i = 0 ; i < count ; ++ i) {
			if ((prime[i]<<1) > n) 
				break;
			if (!visit[n - prime[i]]) {
				flag = prime[i];
				break;
			}
		}
		
		if (flag) printf("%d:\n%d+%d\n", n, flag, n-flag);
		else printf("%d:\nNO WAY!\n",n);
	}
	return 0;
}


UVa 10948 - The primary problem