【欧拉筛】哥德巴赫猜想题解
哥德巴赫猜想题解
题目传送门
1292. 哥德巴赫猜想
一、题目描述
哥德巴赫猜想指出:任意一个大于4的偶数都可以拆成两个奇素数之和。给定多个偶数(6 ≤ n < 10^6),验证它们是否符合这个猜想。对于每个偶数,输出其素数分解中两数差最大的那一组,如果找不到这样的分解,输出错误信息。
二、题目分析
我们需要验证多个偶数是否都能表示为两个素数之和。关键在于:
- 如何高效判断一个数是否为素数
- 如何快速找到满足条件的素数对
- 处理大量输入时的效率问题
三、解题思路
- 使用欧拉筛法预处理所有小于1,000,000的素数,标记非素数
- 对于每个输入n,从最小的奇素数3开始检查,看n-3是否为素数
- 找到第一个满足条件的素数对即可输出,因为从小的素数开始找,自然保证了两数差最大
四、算法讲解
欧拉筛法(线性筛)
- 原理:每个合数只被它的最小质因数筛掉,保证O(n)时间复杂度
- 使用场景:需要预处理大量素数或需要快速判断数是否为素数
- 实现步骤:
- 初始化素数表,标记所有数为素数
- 遍历每个数,如果是素数就加入素数表
- 用当前数和素数表中的数相乘标记合数
- 当当前数能被素数整除时停止标记(保证每个合数只被最小质因数筛掉)
- 例子:筛20以内的素数
- 2是素数,加入列表,标记4
- 3是素数,加入列表,标记6,9(3×3后停止)
- 4不是素数,标记8(2×4)
- 5是素数,标记10,15,25(超过20停止)
- 依此类推…
五、代码实现
#include <bits/stdc++.h>
using namespace std;
// #define int long long
const int N = 1e6 + 10;
int prime[N]; // 存储素数的数组
bool st[N]; // 标记是否为合数,false表示素数
int cnt; // 素数计数器// 欧拉筛法预处理素数
void ola()
{for (int i = 2; i < N; i ++){if (!st[i]) // i是素数{prime[cnt ++] = i; // 加入素数表}// 用当前数和素数表中的数标记合数for (int j = 0; prime[j] * i < N; j ++){st[prime[j] * i] = true; // 标记合数if (i % prime[j] == 0) break; // 保证每个合数只被最小质因数筛掉}}
}void solve()
{int n;ola(); // 预处理素数while (cin >> n, n != 0) // 读取输入直到遇到0{bool flag = 1; // 标记是否找到解// 从3开始检查,每次加2保证是奇数for (int i = 3; i <= n; i ++){// 如果i和n-i都是素数if (!st[i] && !st[n - i]){flag = 0; // 找到解cout << n << " = " << i << " + " << n - i << "\n";break;}}// 如果没有找到解(理论上不会发生)if (flag)cout << "Goldbach's conjecture is wrong.";}
}signed main()
{ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);solve();return 0;
}
六、重点细节
- 欧拉筛法的效率:预处理阶段O(n)时间复杂度,使得后续查询可以在O(1)时间内判断一个数是否为素数
- 素数对的查找:从小的素数开始查找,第一个找到的素数对自然就是差值最大的
- 输入处理:使用快速输入输出优化,处理大量数据时更高效
- 边界情况:题目保证n≥6,所以不需要处理更小的情况
七、复杂度分析
- 时间复杂度:
- 预处理阶段:O(n),使用欧拉筛法
- 查询阶段:最坏情况下O(n/2),但实际运行很快,因为素数分布较密集
- 空间复杂度:O(n),用于存储素数标记和素数表
八、总结
本题通过欧拉筛法预处理素数表,然后对每个查询进行快速验证,有效解决了哥德巴赫猜想的验证问题。算法设计充分利用了数论知识和预处理技巧,保证了在大数据量下的高效运行。
相关文章:
【欧拉筛】哥德巴赫猜想题解
哥德巴赫猜想题解 题目传送门 1292. 哥德巴赫猜想 一、题目描述 哥德巴赫猜想指出:任意一个大于4的偶数都可以拆成两个奇素数之和。给定多个偶数(6 ≤ n < 10^6),验证它们是否符合这个猜想。对于每个偶数,输出其素数分解中两数差最大的…...
A*算法详解及Python实现
一、什么是A*算法? A*(读作"A-star")算法是一种广泛使用的路径查找和图形遍历算法,它结合了Dijkstra算法的完备性和贪婪最佳优先搜索的高效性。A*算法通过使用启发式函数来估算从当前节点到目标节点的成本,…...
【C++】第九节—string类(中)——详解+代码示例
hello! 云边有个稻草人-CSDN博客 C_云边有个稻草人的博客-CSDN博客 菜鸡进化中。。。 目录 【补充】 二、string类里面的常用接口 1.resize 2.insert 3.assign 4.erase 5.replacefind 6.c_str 7.rfindsubstr 8.find_first_of、find_last_of、find_first…...
vite.config.js常用配置
vite 是一个基于 Vue3 单文件组件的非打包开发服务器,它做到了本地快速开发启动: 快速的冷启动,不需要等待打包操作; 即时的热模块更新,替换性能和模块数量的解耦让更新飞起; 真正的按需编译,不…...
【C++11(下)】—— 我与C++的不解之缘(三十二)
前言 随着 C11 的引入,现代 C 语言在语法层面上变得更加灵活、简洁。其中最受欢迎的新特性之一就是 lambda 表达式(Lambda Expression),它让我们可以在函数内部直接定义匿名函数。配合 std::function 包装器 使用,可以…...
李臻20242817_安全文件传输系统项目报告_第6周
安全文件传输系统项目报告(第 1 周) 1. 代码链接 Gitee 仓库地址:https://gitee.com/li-zhen1215/homework/tree/master/Secure-file 代码结构说明: project-root/├── src/ # 源代码目录│ ├── main.c # 主程序入口│ ├…...
使用SymPy求解矩阵微分方程
引言 在数学、物理、工程等领域,微分方程常常被用来描述系统的变化和动态过程。对于多变量系统或者多方程系统,矩阵微分方程是非常常见的,它可以用来描述如电路、控制系统、振动系统等复杂的动态行为。今天,我们将通过Python 中的 SymPy 库来求解矩阵微分方程,帮助大家轻…...
Flutter之用户输入网络数据缓存
目录: 1、处理用户输入1.1、按钮1.2、文本1.3、富文本1.4、TextField1.5、Form 2、复选框、Switch 和 Radio2.1、复选框2.2、Switch2.3、Radio 3、选择日期或时间4、滑动5、网络和数据6、本地缓存6.1、在本地内存中缓存数据 7、web端和Flutter样式控制对比7.1、文本…...
华为IP(4)
VRRP(虚拟路由冗余协议) 前言: 局域网中的用户终端通常采用配置一个默认网关的形式访问外部网络,如果默认网关设备发生故障,那么所有用户终端访问外部网络的流量将会中断。可以通过部署多个网关的方式来解决单点故障…...
蓝桥杯刷题周计划(第四周)
目录 前言题目一题目代码题解分析 题目二题目代码题解分析 题目三题目代码题解分析 题目四题目代码题解分析 题目五题目代码题解分析 题目六题目代码题解分析 题目七题目代码题解分析 题目八题目代码题解分析 题目九题目代码题解分析 题目十题目代码题解分析题目代码题解分析 题…...
华为网路设备学习-17
目录 一、加密算法 二、验证算法 三、IPsec协议 1.IKE协议(密钥交换协议) ①ISAKMP(Internet Security Association and Key Management Protocol)互联网安全关联和密钥管理协议 ②安全关联(SA) ③…...
【动态规划】深入动态规划 非连续子序列问题
文章目录 前言例题一、最长递增子序列二、摆动序列三、最长递增子序列的个数四、最长数对链五、最长定差子序列六、最长的斐波那契子序列的长度七、最长等差数列八、等差数列划分II - 子序列 结语 前言 什么是动态规划中的非连续子序列问题? 动态规划中的非连续子序…...
灵魂拷问,指针为什么是C语言的灵魂?
目录 | 引 言 | 内存操作 | 构造复杂的数据结构 | 底层硬件交互 | 指针的陷阱 | 文 末 | 引 言 指针是C语言的灵魂! 这句话是不是很耳熟?但为什么这么说,你知道吗? 本篇小文就从内存、数据结构、底层硬件交互这三个维度来…...
Node.js自定义中间件
目录 Node.js 自定义中间件详细介绍 1. 目录结构 2. 什么是自定义中间件? 3. 代码实现 1. 自定义日志中间件(记录请求信息) 2. 自定义身份验证中间件(校验用户权限) 3. 自定义请求时间中间件(记录请…...
Qt 音乐播放器项目
具体代码见:https://gitee.com/Suinnnnnn/MusicPlayer 文章目录 0. 预备1. 界面1.1 各部位长度1.2 ui文件1.3 窗口前置设置1.4 设置QSS 2. 自定义控件2.1 按钮2.2 推荐页面2.3 CommonPage2.4 滑杆 3. 音乐管理4. 歌词界面4.1 ui文件4.2 LrcPage.h文件 5. 音乐播放控…...
初识数据结构——Java集合框架解析:List与ArrayList的完美结合
📚 Java集合框架解析:List与ArrayList的完美结合 🌟 前言:为什么我们需要List和ArrayList? 在日常开发中,我们经常需要处理一组数据。想象一下,如果你要管理一个班级的学生名单,或…...
LightRAG实战:轻松构建知识图谱,破解传统RAG多跳推理难题
作者:后端小肥肠 🍊 有疑问可私信或评论区联系我。 🥑 创作不易未经允许严禁转载。 姊妹篇: 2025防失业预警:不会用DeepSeek-RAG建知识库的人正在被淘汰_deepseek-embedding-CSDN博客 从PDF到精准答案:Coze…...
Hyperlane框架全面详解与应用指南 [特殊字符][特殊字符][特殊字符]
Hyperlane框架全面详解与应用指南 🚀🚀🚀 📚 前言 欢迎来到Hyperlane框架的全面详解与应用指南!🎉🎉🎉 本文档旨在为开发者提供一个全面、详尽的Hyperlane框架使用指南,…...
使用LVS的 NAT 模式实现 3 台RS的轮询访问
题目 使用LVS的 NAT 模式实现 3 台RS的轮询访问。IP地址和主机自己规划。 -i— turn,-g——DR模式,-m——NAT模式 节点规划 仅主机网段:192.168.216.0/24 NAT网段:192.168.88.0/24 主机角色系统网络ipclientclientredhat9.5仅…...
BGP路由协议之属性4
MED 多出口鉴别器 可选非过渡属性 EBGP 的邻居 Cost 开销值,控制如何进入 AS。越小越优。继承 IGP 的开销值,默认 0 MED(Multi-Exit Discriminator,多出口鉴别器)是可选非过属性,是一种度量值用于向外部对等体指出进入本 AS 的首…...
数据库的操作
1.创建数据库 CREATE DATABASE [IF NOT EXISTS] db_name [create_specification [,create_specification] ...]create_specification: [DEFAULT] CHARACTER SET charset_name [DEFAULT] COLLATE collation_name 大写的表示关键字。[]是可选项。CHARACTER SET:指定…...
【愚公系列】《高效使用DeepSeek》055-可靠性评估与提升
🌟【技术大咖愚公搬代码:全栈专家的成长之路,你关注的宝藏博主在这里!】🌟 📣开发者圈持续输出高质量干货的"愚公精神"践行者——全网百万开发者都在追更的顶级技术博主! 👉 江湖人称"愚公搬代码",用七年如一日的精神深耕技术领域,以"…...
记录clickhouse记录一次性能优化,从60s到1s
文章目录 问题表结构类似如下分析第一步调整第一步观察多磁盘读继续观察sql 问题 一个查询接口,涉及多个clickhouse 查询,查询用时一下变成要60s 表结构类似如下 CREATE TABLE demo.test_local (id UUID,date DateTime,type String ) ENGINE Replic…...
二叉树的层序遍历
102. Binary Tree Level Order Traversal 广度优先搜索 将每个结点的层号记录下。 /*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode() : val(0), left(nullptr), right(nullptr) {}* …...
嵌入式硬件篇---TOF陀螺仪SPI液晶屏
文章目录 前言1. TOF传感器(Time of Flight)原理STM32使用方法硬件连接SDASCLVCC\GND 软件配置初始化I2C外设库函数驱动:读取数据 2. 陀螺仪(如MPU6050)原理STM32使用方法硬件连接SDA/SCLINTVCC/GND 软件配置初始化I2C…...
OpenCV 在树莓派上进行实时人脸检测
这段 Python 代码借助 OpenCV 库实现了在树莓派上进行实时人脸检测的功能。它会开启摄像头捕获视频帧,在每一帧里检测人脸并以矩形框标记出来,同时在画面上显示帧率(FPS)。 依赖库 cv2:OpenCV 库,用于计算…...
55.跳跃游戏
题目来源: leetcode题目,网址:55. 跳跃游戏 - 力扣(LeetCode) 解题思路: 遍历数组,若当前节点可达,更新可到达的最远距离,否则返回false。若可遍历整个数组…...
awk 实现listagg ,count 功能
awk命令实现分组统计 测试数据 ABC a1 ABC a2 ABC a3 ABD c1 ABD c2 分组统计 abc a1,a2,a3 3 abd c1,c2 awk 命令 awk {arr[$1]arr[$1] ? arr[$1] "," $2 : $2; count[$1]} END{for (i in arr) print tolower(i), arr[i], count[i]} group_…...
瑞萨RA4M2使用心得-GPIO输出
目录 一、新建项目 二、图形化开发 1.初始化IO 2.界面介绍 3.代码编写 4.所有内部函数的封装位置 5.LED闪烁函数编写 三.debug运行 总结 环境: 开发板:RA-Eco-RA4M2-100PIN-V1.0 IDE:e2 studio 一、新建项目 正常操作,下…...
uniapp微信小程序引入vant组件库
1、首先要有uniapp项目,根据vant官方文档使用yarn或npm安装依赖: 1、 yarn init 或 npm init2、 # 通过 npm 安装npm i vant/weapp -S --production# 通过 yarn 安装yarn add vant/weapp --production# 安装 0.x 版本npm i vant-weapp -S --production …...
COZE通关指南:工作流与插件开发
前言 本文隶属于专栏《AI Agent 通关指南》,该专栏为笔者原创,引用请注明来源,不足和错误之处请在评论区帮忙指出,谢谢! 本专栏目录结构和参考文献请见《AI Agent 通关指南》 正文 1. 平台基础介绍 🌟 1.1 COZE平台概述 COZE平台(coze.cn)是一个强大的AI应用开发平台…...
在Unity中,如果物体上的脚本丢失,可以通过编写一个自定义编辑器脚本来查找并删除这些丢失的组件
在Unity中,如果物体上的脚本丢失,可以通过编写一个自定义编辑器脚本来查找并删除这些丢失的组件。以下是一个示例脚本,它可以帮助你一键检索场景中所有丢失脚本的物体,并删除这些丢失的组件。 步骤: 创建编辑器脚本&a…...
青少年编程与数学 02-016 Python数据结构与算法 04课题、栈与队列
青少年编程与数学 02-016 Python数据结构与算法 04课题、栈与队列 一、栈1. 栈的定义2. 栈的特点3. 栈的基本操作示例 4. 栈的实现(1)数组实现(2)链表实现 5. 栈的应用(1)函数调用(2)…...
Lucene.Net全文搜索引擎:架构解析与全流程实战指南
文章目录 引言:为什么选择Lucene.Net?一、Lucene.Net核心架构剖析1.1 模块化设计 二、Lucene.Net索引原理揭秘2.1 倒排索引:搜索的基石2.2 段(Segment)机制 三、全流程实战:从0到1构建搜索引擎3.1 环境准备…...
OpenSceneGraph 中的 LOD详解
LOD (Level of Detail,细节层次) 是3D图形中一种重要的优化技术,OpenSceneGraph 通过 osg::LOD 类提供了完整的LOD支持。 一、LOD 基本概念 1. 什么是LOD 核心思想:根据物体与相机的距离显示不同细节程度的模型 目的:减少远处物…...
程序化广告行业(64/89):AdX/SSP系统广告位设置全解析
程序化广告行业(64/89):AdX/SSP系统广告位设置全解析 大家好!我一直觉得在技术和营销不断融合的当下,程序化广告领域充满了机遇与挑战。之前和大家分享了程序化广告PDB模式的相关知识,今天想接着和大家一起…...
Pytorch中的计算图(Computational Graph)是什么
🧩 一、什么是计算图? 计算图是一种“有向无环图(DAG)”,表示变量(张量)之间的运算关系。 节点:张量或操作(如加法、乘法)边:数据流(即…...
Java 大视界 -- Java 大数据在航天遥测数据分析中的技术突破与应用(177)
💖亲爱的朋友们,热烈欢迎来到 青云交的博客!能与诸位在此相逢,我倍感荣幸。在这飞速更迭的时代,我们都渴望一方心灵净土,而 我的博客 正是这样温暖的所在。这里为你呈上趣味与实用兼具的知识,也…...
【Linux操作系统——学习笔记三】Linux环境下多级目录构建与管理的命令行实践报告
1.在用户主目录下,使用以下方法新建目录,并显示详细执行过程: (1)使用绝对路径在当前目录下创建 new_dir目录 (2)使用相对路径、在当前目录创建dir1、dir2、dir3目录 (3)…...
java.util.Collections中常用api
在Java中,java.util.Collections 是一个工具类,提供了大量静态方法用于操作或返回集合(如List、Set、Map等)。以下是常用的API分类整理: 1. 排序与顺序操作 sort(List<T> list) 对List进行自然顺序排序ÿ…...
批量将图片统一色调
from PIL import Image, ImageEnhance # 确保导入 ImageEnhance 模块 import osdef adjust_image_tone(image_path, output_path, r_weight1.0, g_weight1.0, b_weight1.0, brightness1.0):"""调整图片的色调、明暗,并进行去图处理。参数:image_pat…...
OCC Shape 操作
#pragma once #include <iostream> #include <string> #include <filesystem> #include <TopoDS_Shape.hxx> #include <string>class GeometryIO { public:// 加载几何模型:支持 .brep, .step/.stp, .iges/.igsstatic TopoDS_Shape L…...
docker的run命令 笔记250406
docker的run命令 笔记250406 Docker 的 run 命令用于创建并启动一个新的容器。它是 Docker 中最常用的命令之一,基本语法为: docker run [OPTIONS] IMAGE [COMMAND] [ARG...]常用选项(OPTIONS) 参数说明-d 或 --detach后台运行…...
批量将 HTML 转换为 Word/Txt/PDF 等其它格式
HTML是一种超文本标记语言,在进行网页编辑的时候非常常见,我们浏览的网站内容,都可以保存为 html 格式,如果想要将 html 格式的文档转为其它格式,比如 Word、PDF 或者 Txt,我们应该怎么做呢?今天…...
TPS入门DAY02 服务器篇
1.创建空白插件 2.导入在线子系统以及在线steam子系统库 MultiplayerSessions.uplugin MultiplayerSessions.Build.cs 3.创建游戏实例以及初始化会话创建流程 创建会话需要的函数,委托,委托绑定的回调,在线子系统接口绑定某一个委托的控制其…...
C高级,终端操作
核心要点整理 刷题作业 一、基础操作 命令行提示符结构 ubuntuubuntu:~$ 当前用户 | 连接符 | 计算机名 | 当前路径 | 用户权限 用户切换 su 用户名:切换用户sudo passwd 用户名:修改用户密码 常用指令 cd -:返回上一次路径ls:显…...
Lua语言的边缘计算
Lua语言的边缘计算探索 引言 随着物联网(IoT)、人工智能(AI)和大数据技术迅速发展,边缘计算作为一种分布式计算架构日益受到重视。其核心理念是将计算和数据存储资源更靠近数据源,以降低延迟、减轻网络负…...
RabbitMQ运维
RabbitMQ运维 一.集群1.简单介绍2.集群的作用 二.搭建集群1.多机多节点搭建步骤 2.单机单节点搭建步骤 3.宕机演示 三.仲裁队列1.简单介绍2.Raft协议Raft基本概念主节点选举选举过程 3.仲裁队列的使用 四.HAProxy负载均衡1.安装HAProxy2.HAProxy的使用 一.集群 1.简单介绍 Ra…...
【ESP32】ESP32物联网应用:MQTT控制与状态监测
ESP32物联网应用:MQTT控制与状态监测 引言 在物联网时代,远程监测和控制设备已经成为现实生活中常见的需求。本文将介绍如何使用ESP32微控制器配合MQTT协议,实现一个简单而强大的物联网应用:远程状态监测和设备控制。我们将以巴…...
如何保证RabbitMQ消息的可靠传输?
在这个图中,消息可能丢失的场景是1,2,3 1.在生产者将消息发送给RabbitMQ的时候,消息到底有没有正确的到达服务器呢,RabbitMQ提供了两种解决方案: a. 通过事务机制实现(比较消耗性能࿰…...