首页 > 其他分享 >哥德巴赫猜想2(另一种)(猜想专题3)

哥德巴赫猜想2(另一种)(猜想专题3)

时间:2024-08-01 19:28:09浏览次数:13  
标签:parity 专题 return 猜想 哥德巴赫猜想 int 质数 && isprime

大家好,小编也是更新了好吧(主要是因为CSP,当然再找个c++能解决的猜想也挺难的)。

今天给大家带来的是哥德巴赫猜想的另一种情况,题目如下:

每个大于7的奇数都能表示3个不同奇质数之和,如9=3+3+3,15=3+5+7等。

其实转化后就相当于2n - 1 = a + b + c(a,b,c均为质数)。

既然这样,我们先编以下判断质数的程序:

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

编好了。

当然,在《哥德巴赫猜想(猜想专题1)》时已经有过解释了。

接下来就不同了,因为它是3个数,应该是这样的:

for(int i = 1;i <= n;i++){
	for(int j = 1;j <= n;j++){
		for(int k = 1;k <= n;k++){
				
		}
	}
}

但在正常题目里他的复杂度为O(n ^ 3),非常容易超时,因此我们需要想个方法简化一下这个三重循环。

我们发现,当i,j都确定后,k刚好是原数n-i-j,那我们就简化成双重循环:

for(int i = 1;i <= n;i++){
	for(int j = 1;j <= n;j++){
		int k = n - i - j;
			
	}
}

这样复杂度变为O(n ^ 2),大大提升了运算速度。

那接下来就是判断,很简单一笔带过:

if(isprime(i) && isprime(j) && isprime(k)){
	cout << n << "=" << i << "+" << j << "+" << k << endl;
	return 0;
}

接下来,完工了......吗?

我们再看一遍题目,发现是3个奇质数之和,所以还得判断一下三个数的奇偶性:

int parity(int n){
	if(n % 2 == 1) return true;
	return false;
}

写到这里,再把判断改一下,也总算是完成了......么?

我们发现题目说的是3个不同奇质数之和,所以还要加3个个判断,最后获得了非常长的一个判断:

if(isprime(i) && isprime(j) && isprime(k) && parity(i) && parity(j) && parity(k) && i != j && j != k && i != k){
	cout << n << "=" << i << "+" << j << "+" << k << endl;
	return 0;
}

这里才算真正编完了,下面是完整代码:

#include <iostream>
using namespace std;

int parity(int n){
	if(n % 2 == 1) return true;
	return false;
}

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

int main(){
	int n;
	cin >> n;
	for(int i = 1;i <= n;i++){
		for(int j = 1;j <= n;j++){
			int k = n - i - j;
			if(isprime(i) && isprime(j) && isprime(k) && parity(i) && parity(j) && parity(k) && i != j && j != k && i != k){
				cout << n << "=" << i << "+" << j << "+" << k << endl;
				return 0;
			}
		}
	}
	
}

好了,今天小编的分享就到这里,再见!

标签:parity,专题,return,猜想,哥德巴赫猜想,int,质数,&&,isprime
From: https://blog.csdn.net/breeze_phantom/article/details/140821196

相关文章

  • 行李托运问题(c++实际问题专题1)
    大家好,小编今天给大家带来一个问题,这个问题出题方法也比较实用。先看一下题干: 这道题目其实分一下货物的类型就行了,<=10的算一类,>10的算一类,这样在分别算出就行,先算<=10的:if(n<=10)cout<<fixed<<setprecision(2)<<2.5;//注意,这里需要用fixed-setpresicion函数......
  • 专题(十八)时间
    一、date命令1、计算到目前的毫秒(date+%s%3N)一般可以用于统计执行某个命令的耗费时间_start_time=`date+%s%3N`........................................_end_time=`date+%s%3N`_diff=$((_end_time-_start_time))  一、案例1、查询服务器启动之后,某个服务是......
  • 【专题】2023年中国数字金融调查报告PDF合集分享(附原数据表)
    原文链接:https://tecdat.cn/?p=34685原文出处:拓端数据部落公众号随着数字化转型的深入推进,新客户的增长速度已达顶峰,用户运营成为推动存量增长的关键手段。调查数据显示,相比去年,网上银行用户比例有所下降,而手机银行用户比例基本持平。阅读原文,获取专题报告合集全文,解锁文末249份......
  • 企业数字化转型的必备钥匙:数据思维|专题报告集
    原文链接:https://tecdat.cn/?p=37165本质上来讲,企业数字化转型,不仅是技术方面的升级,更是企业文化、思维方式的转变。那么,企业数字化转型究竟需要什么样的思维方式?企业数字化转型,需要什么样的思维方式?不知道你有没有过这样的感觉:不知道从什么时候开始,和人沟通过程,以及要说服别人......
  • 补环境专题
    目录付费第一课-浏览器与事件付费第二课-Proxy代理器付费第三课-作业详解付费第四课-Hook框架付费课第五课-框架设计付费课第六课-脱环境专题1付费课第七课-脱环境专题2付费课第八课-HTML解析为DOM树付费课第九课-HTML解析为DOM树2付费课第十课--浏览器事件补全(附加ja3......
  • 【专题】2024家·生活智能家居趋势报告合集PDF分享(附原数据表)
    原文链接: https://tecdat.cn/?p=37146近二十载间,中国消费市场见证了从产品创新到渠道创新的双重飞跃,无论是耐用消费品还是快速消费品,均在线上线下平台绽放出前所未有的丰富选择,多数行业已转型为以消费者为核心导向的买方市场格局。阅读原文,获取专题报告合集全文,解锁文末218份智......
  • 【K8s】专题七(4):Kubernetes 服务发现之 Ingress 进阶
    以下内容均来自个人笔记并重新梳理,如有错误欢迎指正!如果对您有帮助,烦请点赞、关注、转发!欢迎扫码关注个人公众号!目录一、官方文档二、Ingress进阶使用(示例)1、Ingress实现重定向2、Ingress实现路由跳转3、Ingress实现自定义配置4、Ingress实现CORS5、Ingress实......
  • 暑假集训第一周专题:树
    暑假集训第一周专题:树本专题其实还是看中对题目的阅读理解能力,dfs实现起来很简单,主要是知道题目到底要干嘛A.KuroandWalkingRoute题面输入输出思路即所有路线减去经过x到y的路线由x到y的路线,包括从某些点到x,经过一些点再到y,从y再到某些点有根据题目......
  • 代码随想录算法训练营第47天 | 动态序列11:序列专题2
    代码随想录算法训练营第天|1143.最长公共子序列https://leetcode.cn/problems/longest-common-subsequence/description/代码随想录https://programmercarl.com/1143.最长公共子序列.html#算法公开课1035.不相交的线https://leetcode.cn/problems/uncrossed-lines/descrip......
  • dp专题
    1.花店橱窗原题链接:https://ac.nowcoder.com/acm/contest/87275/1005注意放与不放是平行的查看代码#include<bits/stdc++.h>#defineintlonglongusingnamespacestd;intva[110][110];intf[1000000];structnode{inta[110];intt;}way[110][110];//......