蓝桥杯 — — 纯质数
纯质数
题目:
思路:
一个最简单的思路就是枚举出所有的质数,然后再判断这个质数是否是一个纯质数。
-
枚举出所有的质数:
可以使用常规的暴力求解法,其时间复杂度为( O ( N N ) O(N\sqrt{N}) O(NN)),而埃氏筛法的时间复杂度为( O ( N log log n ) O(N \log \log n) O(Nloglogn)),如果需要判断单个数是否为素数,试除法是更合适的选择;而如果需要求解一定范围内的素数,则埃拉托斯特尼筛法效率更高。这里我们使用埃氏筛法求解给定范围内的所有素数。
-
判断纯质数:
一个直接的思路是,遍历质数的每一位,判断该位置上的数是否为质数,因为对于每一位,如果是质数的话,那么这些数是固定的,即:
2
3
5
7
,我们可以将其写入到一个哈希表中,可以使用map
库进行存储(map
的查询操作的时间复杂度为( O ( log N ) O(\log N) O(logN))),也可以自定义一个哈希数组进行查找(哈希查找的时间复杂度为( O ( 1 ) O(1) O(1)))
埃氏筛法:对一个给定的范围,求其中的质数,我们从
2
开始进行遍历,遍历到的每一个数,如果是质数,我们都将其进行添加到数组中,接着对数组中已经记录的所有质数进行乘积,如果得到的结果小于给定的范围,那么就标记这个值为合数,继续遍历下一个数,直到边界时停止。
例子:如果我们要求
20
以内的所有质数,我们首先设定一个标记数组cnt[20]
,并令其初值都为0
,表示目前的所有数都是一个质数,然后从2
开始进行遍历,首先判断2
是否是一个质数,可以知道2
是一个质数,将2
添加到质数数组ans
中,然后遍历结果数组,得到2 * 2 = 4 < 20
,标记4
为一个合数(即:令cnt[4] = 1
),接着进入下一个循环,判断3
是一个质数,将3
添加到ans
中,遍历ans
,3 * 2 = 6 < 20
,标记6
为一个合数,3 * 3 = 9 < 20
,标记9
为一个合数,进入下一个循环,判断4不是一个质数,直接进行遍历ans
数组,2 * 4 = 8 < 20
,3 * 4 = 12 < 20
,4 * 4 = 16 < 20
,分别将8,12,16
进行标记,表示这些数是一个合数。依次类推知道遍历到最后即可得到所有的质数了(ans
数组中记录的即是所有的质数)
GPT的一个解释:
代码:
- 使用map进行判断是否是纯质数
// 纯质数
#include<iostream>
#include<vector>
#include<map>
#include<string>
using namespace std;
//为了方便找到纯质数,我们需要一个映射 vector<int> primeNumbers(int lb, int rb){vector<int> PN;// 定义一个数组,用于标记是否是一个质数vector<int> cnt(rb + 10, 0); // 初始的值设定为0,表示都为质数 for(int i = 2;i <= rb;i ++){if(!cnt[i]){ // 如果是质数就进行标记,并且添加到数组中PN.push_back(i);cnt[i] = 1; }// 标记出不是质数的数for(auto v : PN){if(v * i > rb) break;cnt[v * i] = 1; // 首先要判断是否越界}}// 最后得到一个质数的数组PNreturn PN;
}// 判单纯质数
map<int, int> smallPrimeNumber = {{2, 1}, {3, 1}, {5, 1}, {7, 1}};
bool purePrimeNumber(int num){int temp;while(num){temp = num % 10;if(smallPrimeNumber.find(temp) == smallPrimeNumber.end()) return 0;num /= 10;}return 1;
}
void solve(){// leads:首先找到所有的质数,然后再进行寻找所有的纯质数const int lb = 1;const int rb = 20210605;int ans = 0;vector<int> ansPN = primeNumbers(lb, rb);for(auto v : ansPN){if(purePrimeNumber(v)) ans++;}cout<<ans<<endl;return ;
}int main(){ios::sync_with_stdio(false);cin.tie(0);int t = 1;while(t--){solve();} return 0;
}
- 使用一个哈希表判断是否是纯质数
// 纯质数
#include<iostream>
#include<vector>
#include<map>
#include<string>
using namespace std;
//为了方便找到纯质数,我们需要一个映射
map<int, bool> PPNM; vector<int> primeNumbers(int lb, int rb){vector<int> PN;// 定义一个数组,用于标记是否是一个质数vector<int> cnt(rb + 10, 0); // 初始的值设定为0,表示都为质数 for(int i = 2;i <= rb;i ++){if(!cnt[i]){ // 如果是质数就进行标记,并且添加到数组中PN.push_back(i);cnt[i] = 1; }// 标记出不是质数的数for(auto v : PN){if(v * i > rb) break;cnt[v * i] = 1; // 首先要判断是否越界}}// 最后得到一个质数的数组PNreturn PN;
}// 判单纯质数
int hashMap[10] = {0, 0, 1, 1, 0, 1, 0 ,1 ,0 ,0};
bool purePrimeNumber(int num){int temp;while(num){temp = num % 10;num /= 10;if(!hashMap[temp]) return false;}return true;
}void solve(){// leads:首先找到所有的质数,然后再进行寻找所有的纯质数const int lb = 1;const int rb = 20210605;int ans = 0;vector<int> ansPN = primeNumbers(lb, rb);for(auto v : ansPN){if(purePrimeNumber(v)) ans++;}cout<<ans<<endl;return ;
}int main(){ios::sync_with_stdio(false);cin.tie(0);int t = 1;while(t--){solve();} return 0;
}
相关文章:

蓝桥杯 — — 纯质数
纯质数 题目: 思路: 一个最简单的思路就是枚举出所有的质数,然后再判断这个质数是否是一个纯质数。 枚举出所有的质数: 可以使用常规的暴力求解法,其时间复杂度为( O ( N N ) O(N\sqrt{N}) O(NN )&…...

OpenCV基本图像处理操作(三)——图像轮廓
轮廓 cv2.findContours(img,mode,method) mode:轮廓检索模式 RETR_EXTERNAL :只检索最外面的轮廓;RETR_LIST:检索所有的轮廓,并将其保存到一条链表当中;RETR_CCOMP:检索所有的轮廓,并将他们组…...

比特币突然暴跌
作者:秦晋 周末愉快。 今天给大家分享两则比特币新闻,也是两个数据。一则是因为中东地缘政治升温,传统资本市场的风险情绪蔓延至加密市场,引发加密市场暴跌。比特币跌至66000美元下方。杠杆清算金额高达8.5亿美元。 二则是&#x…...

使用SpeechRecognition和vosk处理ASR
SpeechRecognition可以支持多种模型语音转文字,感觉vosk还不错,使用起来也简单一些;百度也有PaddleSpeech,但是安装起来太麻烦,不是这个库版本不对就是那个库有问题,用起来不方便; 安装SpeechR…...
【Go】通道:缓冲通道和非缓冲通道
目录 通道的基本概念 缓冲通道 非缓冲通道 总结 通道的基本概念 在Go语言中,通道是一种特殊的类型,用于在goroutine之间传递数据。你可以将通道想象为数据的传输管道。通道分为两种类型: 非缓冲通道(Unbuffered Channels&…...
Java中数组的使用
在Java编程中,数组是一种非常重要的数据结构,它允许我们存储相同类型的多个元素。对于初学者来说,理解数组的基本概念、初始化、遍历、默认值以及内存分配和使用注意事项是非常关键的。 一、数组的概念 数组是一个可以容纳多个相同类型数据…...
CAP5_Monday
A Set to Max (Easy Version) 给定数组 a 和 b,可以执行以下操作任意次 : 让 a l ∼ a r a_l\sim a_r al∼ar 中的所有所有元素变成 a i a_i ai ( l ≤ i ≤ r ) (l\leq i\leq r) (l≤i≤r), 其中 1 ≤ l ≤ r ≤ n 1\leq l \leq r \leq n 1≤…...

科大讯飞星火开源大模型iFlytekSpark-13B GPU版部署方法
星火大模型的主页:iFlytekSpark-13B: 讯飞星火开源-13B(iFlytekSpark-13B)拥有130亿参数,新一代认知大模型,一经发布,众多科研院所和高校便期待科大讯飞能够开源。 为了让大家使用的更加方便,科…...

SpringBoot基于RabbitMQ实现消息延迟队列方案
知识小科普 在此之前,简单说明下基于RabbitMQ实现延时队列的相关知识及说明下延时队列的使用场景。 延时队列使用场景 在很多的业务场景中,延时队列可以实现很多功能,此类业务中,一般上是非实时的,需要延迟处理的&a…...
Go语言使用标准库时常见错误
Go的标准库是一组增加和拓展语言的核心包。然而,很容易误用标准库,或者我们对其行为理解有限,导致产生了bug或不应该在生产级应用程序中某些功能。 1. 提供错误的持续时间 标准库提供了获取 time.Duration 的常用函数和方法,但由于 time.Duration 是 int64 的自定义类型,…...

UE5不打包启用像素流 ubuntu22.04
首先查找引擎中像素流的位置: zkzk-ubuntu2023:/media/zk/Data/Linux_Unreal_Engine_5.3.2$ sudo find ./ -name get_ps_servers.sh [sudo] zk 的密码: ./Engine/Plugins/Media/PixelStreaming/Resources/WebServers/get_ps_servers.sh然后在指定路径中…...
Redis 常用数据类型常用命令和应用场景
首先先混个眼熟 Redis 中的 8 种常用数据类型: 5 种基础数据类型:String(字符串)、List(列表)、Set(集合)、Hash(散列)、Zset(有序集合࿰…...

ins视频批量下载,instagram批量爬取视频信息
简介 Instagram 是目前最热门的社交媒体平台之一,拥有大量优质的视频内容。但是要逐一下载这些视频往往非常耗时。在这篇文章中,我们将介绍如何使用 Python 编写一个脚本,来实现 Instagram 视频的批量下载和信息爬取。 我们使用selenium获取目标用户的 HTML 源代码,并将其保存…...
Canvas图形编辑器-数据结构与History(undo/redo)
Canvas图形编辑器-数据结构与History(undo/redo) 这是作为 社区老给我推Canvas,于是我也学习Canvas做了个简历编辑器 的后续内容,主要是介绍了对数据结构的设计以及History能力的实现。 在线编辑: https://windrunnermax.github.io/CanvasEditor开源地…...

阿里云Centos7下编译glibc
编译glibc 原来glibc版本 编译前需要的环境: CentOS7 gcc 8.3.0 gdb 8.3.0 make 4.0 binutils 2.39 (ld -v) python 3.6.8 其他看INSTALL, 但有些版本也不易太高 wget https://mirrors.aliyun.com/gnu/glibc/glibc-2.37.tar.gz tar -zxf glibc-2.37.tar.gz cd glibc-2.37/ …...

UE5数字孪生系列笔记(四)
场景的切换 创建一个按钮的用户界面UMG 创建一个Actor,然后将此按钮UMG添加到组件Actor中 调节几个全屏的背景 运行结果 目标点切换功能制作 设置角色到这个按钮的位置效果 按钮被点击就进行跳转 多个地点的切换与旋转 将之前的目标点切换逻辑替换成旋转的逻…...

品牌故事化:Kompas.ai如何塑造深刻的品牌形象
在这个信息爆炸的时代,品牌故事化已经成为企业塑造独特形象、与消费者建立情感联系的重要手段。一个引人入胜的品牌故事不仅能够吸引消费者的注意力,还能够在消费者心中留下持久的印象,建立起强烈的情感连接。本文将深入探讨品牌故事化对于构…...
5g和2.4g频段有什么区别
运行的频段不同 2.4G和5G频段的主要区别在于它们运行的频段不同,2.4G频段运行在2.4GHz的频段上,而5G频段(这里指的是5GHz频段)运行在5GHz的频段上。12 这导致了两者在传输速度、覆盖范围、抗干扰能力等方面的明显差异。以下是详…...

交通管理在线服务系统|基于Springboot的交通管理系统设计与实现(源码+数据库+文档)
交通管理在线服务系统目录 目录 基于Springboot的交通管理系统设计与实现 一、前言 二、系统功能设计 三、系统实现 1、用户信息管理 2、驾驶证业务管理 3、机动车业务管理 4、机动车业务类型管理 四、数据库设计 1、实体ER图 五、核心代码 六、论文参考 七、最新计…...
konva.js 工具类
konva.js 工具类 class KonvaCanvas {/*** 初始化画布* param {String} domId 容器dom id*/constructor(domId) {this.layer null;this.stage null;this.scale 1;this.init(domId);}/*** 聚焦到指定元素* param {String} elementId 元素dom id*/focusOn(elementId) {if (!t…...

地震勘探——干扰波识别、井中地震时距曲线特点
目录 干扰波识别反射波地震勘探的干扰波 井中地震时距曲线特点 干扰波识别 有效波:可以用来解决所提出的地质任务的波;干扰波:所有妨碍辨认、追踪有效波的其他波。 地震勘探中,有效波和干扰波是相对的。例如,在反射波…...

CMake 从 GitHub 下载第三方库并使用
有时我们希望直接使用 GitHub 上的开源库,而不想手动下载、编译和安装。 可以利用 CMake 提供的 FetchContent 模块来实现自动下载、构建和链接第三方库。 FetchContent 命令官方文档✅ 示例代码 我们将以 fmt 这个流行的格式化库为例,演示如何: 使用 FetchContent 从 GitH…...
IP如何挑?2025年海外专线IP如何购买?
你花了时间和预算买了IP,结果IP质量不佳,项目效率低下不说,还可能带来莫名的网络问题,是不是太闹心了?尤其是在面对海外专线IP时,到底怎么才能买到适合自己的呢?所以,挑IP绝对是个技…...

【C++】纯虚函数类外可以写实现吗?
1. 答案 先说答案,可以。 2.代码测试 .h头文件 #include <iostream> #include <string>// 抽象基类 class AbstractBase { public:AbstractBase() default;virtual ~AbstractBase() default; // 默认析构函数public:virtual int PureVirtualFunct…...
Docker拉取MySQL后数据库连接失败的解决方案
在使用Docker部署MySQL时,拉取并启动容器后,有时可能会遇到数据库连接失败的问题。这种问题可能由多种原因导致,包括配置错误、网络设置问题、权限问题等。本文将分析可能的原因,并提供解决方案。 一、确认MySQL容器的运行状态 …...

恶补电源:1.电桥
一、元器件的选择 搜索并选择电桥,再multisim中选择FWB,就有各种型号的电桥: 电桥是用来干嘛的呢? 它是一个由四个二极管搭成的“桥梁”形状的电路,用来把交流电(AC)变成直流电(DC)。…...

云原生时代的系统设计:架构转型的战略支点
📝个人主页🌹:一ge科研小菜鸡-CSDN博客 🌹🌹期待您的关注 🌹🌹 一、云原生的崛起:技术趋势与现实需求的交汇 随着企业业务的互联网化、全球化、智能化持续加深,传统的 I…...

【threejs】每天一个小案例讲解:创建基本的3D场景
代码仓 GitHub - TiffanyHoo/three_practices: Learning three.js together! 可自行clone,无需安装依赖,直接liver-server运行/直接打开chapter01中的html文件 运行效果图 知识要点 核心三要素 场景(Scene) 使用 THREE.Scene(…...

【Vue】scoped+组件通信+props校验
【scoped作用及原理】 【作用】 默认写在组件中style的样式会全局生效, 因此很容易造成多个组件之间的样式冲突问题 故而可以给组件加上scoped 属性, 令样式只作用于当前组件的标签 作用:防止不同vue组件样式污染 【原理】 给组件加上scoped 属性后…...
Linux信号保存与处理机制详解
Linux信号的保存与处理涉及多个关键机制,以下是详细的总结: 1. 信号的保存 进程描述符(task_struct):每个进程的PCB中包含信号相关信息。 pending信号集:记录已到达但未处理的信号(未决信号&a…...