CF735D Taxes,哥德巴赫猜想

哥德巴赫猜想:
一个偶数(>2)都可以拆成两个质数的和
一个奇数(>5)都可以拆成三个质数的和
但这里注意:
一个奇数还可能拆成:质数2+质数

原话:任一大于2的偶数都可写成两个质数之和,:任一大于5的整数都可写成三个质数之和

然后就分四种情况:
n是质数:1
n是偶数:2(两个质数)
n是奇数:n-2是质数:可以拆成2+质数        2
.                n-2不是质数:不可以拆成2+质数    3
#include <iostream>

using namespace std;

long long n;

bool isprime(int x){
	for(int i=2;i<=x/i;i++){
		if(x%i==0) {
			return false;	
		}
	}
	return true;
}

int main(int argc, char** argv) {
	cin>>n;
	if(isprime(n)) cout<<"1"<<endl;
	else if(n%2==0||isprime(n-2)) cout<<"2"<<endl;
	else puts("3");
	return 0;
}


全部评论

相关推荐

RickieOne:还有一个面试,上来就笔试算法 1️⃣ 字符串分割不能用 split ,ab&&c,根据&&放到数组上 2️⃣a 到 z 的全部组合情况,包括 a...z 3️⃣多线程,同时打印 1-200 4️⃣sql 代码 考分组 聚合 平均结合 小厂也这样吗,然后就八股 再拷打项目
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客企业服务