henuoj 1166 TonyStark with Prime(Hard Edition) 哥德巴赫猜想

题目链接

哥德巴赫猜想：任何一个大于2的偶数能拆成两个素数之和

正好可以用在本题

（题目描述中说的任何一个大于3的数能拆分乘两个素数和是错误的，举个例子，11，如果想拆分成两个数的和必须是一个奇数一个偶数，偶数素数只有2，奇数只能是9，显然不成立）

本题目中给定一个数字 n ，(n <= 1e12)，求这个数字能否由四个素数组成，如果能，输出所有方案中的任何一个，如果不能输出3000.

首先，最小的素数是2，所以2 * 4 = 8，要想组成最小是8，小于8无法完成输出3000，对于大于8的都可以。

原因：如果大于8是一个偶数，拆分成两个偶数，利用哥德巴赫猜想可以明显看出可以，如果是奇数，先拆分出一个2一个3，剩下的又是一个偶数拆分成两个素数，很明显可以。

我们怎么求满足条件的数字呢？

首先预处理一个区间内的所有素数（埃式筛），对输入的数字 n 进行判断，如果小于8就输出3000，否则判断奇偶性，如果是偶数，就把偶数拆分成为两个偶数 t1 , t2 ，对每一个偶数，循环遍历刚刚区间内的全部数字，如果有一个 数满足 (t1 - i)是素数，则记录下来跳出循环，另外一个偶数同样操作，如果是奇数，首先得到两个数2 和 3，然后 n -= 5，回到刚刚的一个步骤求解即可。

#include 
#include 
#include 
#include 
#include 
using namespace std;
typedef long long ll;
ll n;
ll v[1000000];
void pre_work(){v[0] = -1;v[1] = -1;for (int i = 2; i < 1000000; i++){if(v[i] != 0)continue;v[i] = 1;for (int j = 2; j * i < 1000000; j++){v[i * j] = -1;}}
}
int is(ll num){if(num == 1)return 0;if(num == 0)return 0;if(num == 2)return 1;ll sq = sqrt(num);for (ll i = 2; i <= sq; i++){if(num % i == 0)return 0;}return 1;
}
int main()
{vector prime;pre_work();for (int i = 2; i < 1000000; i++)if(v[i] == 1)prime.push_back(i);while (cin >> n){if(n < 8){cout << "3000" << endl;continue;}if(n & 1){ll a, b, c, d;a = 2;b = 3;n -= 5;for (ll i : prime){if(is(n - i)){c = i;d = n - i;break;}}printf("%lld %lld %lld %lld\n", a, b, c, d);}else{ll a, b, c, d;ll t1 = n / 2;ll t2 = t1;if(t1 & 1){t1++;t2--;}for (ll i : prime){if(is(t1 - i)){a = i;b = t1 - i;break;}}for (ll i : prime){if(is(t2 - i)){c = i;d = t2 - i;break;}}printf("%lld %lld %lld %lld\n", a, b, c, d);}}return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！