当前位置: 首页 > news >正文

蓝桥杯 — — 纯质数

纯质数

题目:

在这里插入图片描述

思路:

一个最简单的思路就是枚举出所有的质数,然后再判断这个质数是否是一个纯质数。

  1. 枚举出所有的质数:

    可以使用常规的暴力求解法,其时间复杂度为( O ( N N ) O(N\sqrt{N}) O(NN )),而埃氏筛法的时间复杂度为( O ( N log ⁡ log ⁡ n ) O(N \log \log n) O(Nloglogn)),如果需要判断单个数是否为素数,试除法是更合适的选择;而如果需要求解一定范围内的素数,则埃拉托斯特尼筛法效率更高。这里我们使用埃氏筛法求解给定范围内的所有素数。

  2. 判断纯质数:

    一个直接的思路是,遍历质数的每一位,判断该位置上的数是否为质数,因为对于每一位,如果是质数的话,那么这些数是固定的,即: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中,遍历ans3 * 2 = 6 < 20,标记6为一个合数,3 * 3 = 9 < 20,标记9为一个合数,进入下一个循环,判断4不是一个质数,直接进行遍历ans数组,2 * 4 = 8 < 203 * 4 = 12 < 204 * 4 = 16 < 20,分别将8,12,16进行标记,表示这些数是一个合数。依次类推知道遍历到最后即可得到所有的质数了(ans数组中记录的即是所有的质数)

GPT的一个解释:

在这里插入图片描述

代码:

  1. 使用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;
}

在这里插入图片描述

  1. 使用一个哈希表判断是否是纯质数
// 纯质数
#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;
}

在这里插入图片描述

相关文章:

蓝桥杯 — — 纯质数

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

OpenCV基本图像处理操作(三)——图像轮廓

轮廓 cv2.findContours(img,mode,method) mode:轮廓检索模式 RETR_EXTERNAL &#xff1a;只检索最外面的轮廓&#xff1b;RETR_LIST&#xff1a;检索所有的轮廓&#xff0c;并将其保存到一条链表当中&#xff1b;RETR_CCOMP&#xff1a;检索所有的轮廓&#xff0c;并将他们组…...

比特币突然暴跌

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

使用SpeechRecognition和vosk处理ASR

SpeechRecognition可以支持多种模型语音转文字&#xff0c;感觉vosk还不错&#xff0c;使用起来也简单一些&#xff1b;百度也有PaddleSpeech&#xff0c;但是安装起来太麻烦&#xff0c;不是这个库版本不对就是那个库有问题&#xff0c;用起来不方便&#xff1b; 安装SpeechR…...

【Go】通道:缓冲通道和非缓冲通道

目录 通道的基本概念 缓冲通道 非缓冲通道 总结 通道的基本概念 在Go语言中&#xff0c;通道是一种特殊的类型&#xff0c;用于在goroutine之间传递数据。你可以将通道想象为数据的传输管道。通道分为两种类型&#xff1a; 非缓冲通道&#xff08;Unbuffered Channels&…...

Java中数组的使用

在Java编程中&#xff0c;数组是一种非常重要的数据结构&#xff0c;它允许我们存储相同类型的多个元素。对于初学者来说&#xff0c;理解数组的基本概念、初始化、遍历、默认值以及内存分配和使用注意事项是非常关键的。 一、数组的概念 数组是一个可以容纳多个相同类型数据…...

CAP5_Monday

A Set to Max (Easy Version) 给定数组 a 和 b&#xff0c;可以执行以下操作任意次 : 让 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)&#xff0c; 其中 1 ≤ l ≤ r ≤ n 1\leq l \leq r \leq n 1≤…...

科大讯飞星火开源大模型iFlytekSpark-13B GPU版部署方法

星火大模型的主页&#xff1a;iFlytekSpark-13B: 讯飞星火开源-13B&#xff08;iFlytekSpark-13B&#xff09;拥有130亿参数&#xff0c;新一代认知大模型&#xff0c;一经发布&#xff0c;众多科研院所和高校便期待科大讯飞能够开源。 为了让大家使用的更加方便&#xff0c;科…...

SpringBoot基于RabbitMQ实现消息延迟队列方案

知识小科普 在此之前&#xff0c;简单说明下基于RabbitMQ实现延时队列的相关知识及说明下延时队列的使用场景。 延时队列使用场景 在很多的业务场景中&#xff0c;延时队列可以实现很多功能&#xff0c;此类业务中&#xff0c;一般上是非实时的&#xff0c;需要延迟处理的&a…...

Go语言使用标准库时常见错误

Go的标准库是一组增加和拓展语言的核心包。然而,很容易误用标准库,或者我们对其行为理解有限,导致产生了bug或不应该在生产级应用程序中某些功能。 1. 提供错误的持续时间 标准库提供了获取 time.Duration 的常用函数和方法,但由于 time.Duration 是 int64 的自定义类型,…...

UE5不打包启用像素流 ubuntu22.04

首先查找引擎中像素流的位置&#xff1a; zkzk-ubuntu2023:/media/zk/Data/Linux_Unreal_Engine_5.3.2$ sudo find ./ -name get_ps_servers.sh [sudo] zk 的密码&#xff1a; ./Engine/Plugins/Media/PixelStreaming/Resources/WebServers/get_ps_servers.sh然后在指定路径中…...

Redis 常用数据类型常用命令和应用场景

首先先混个眼熟 Redis 中的 8 种常用数据类型&#xff1a; 5 种基础数据类型&#xff1a;String&#xff08;字符串&#xff09;、List&#xff08;列表&#xff09;、Set&#xff08;集合&#xff09;、Hash&#xff08;散列&#xff09;、Zset&#xff08;有序集合&#xff0…...

ins视频批量下载,instagram批量爬取视频信息

简介 Instagram 是目前最热门的社交媒体平台之一,拥有大量优质的视频内容。但是要逐一下载这些视频往往非常耗时。在这篇文章中,我们将介绍如何使用 Python 编写一个脚本,来实现 Instagram 视频的批量下载和信息爬取。 我们使用selenium获取目标用户的 HTML 源代码,并将其保存…...

Canvas图形编辑器-数据结构与History(undo/redo)

Canvas图形编辑器-数据结构与History(undo/redo) 这是作为 社区老给我推Canvas&#xff0c;于是我也学习Canvas做了个简历编辑器 的后续内容&#xff0c;主要是介绍了对数据结构的设计以及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&#xff0c;然后将此按钮UMG添加到组件Actor中 调节几个全屏的背景 运行结果 目标点切换功能制作 设置角色到这个按钮的位置效果 按钮被点击就进行跳转 多个地点的切换与旋转 将之前的目标点切换逻辑替换成旋转的逻…...

品牌故事化:Kompas.ai如何塑造深刻的品牌形象

在这个信息爆炸的时代&#xff0c;品牌故事化已经成为企业塑造独特形象、与消费者建立情感联系的重要手段。一个引人入胜的品牌故事不仅能够吸引消费者的注意力&#xff0c;还能够在消费者心中留下持久的印象&#xff0c;建立起强烈的情感连接。本文将深入探讨品牌故事化对于构…...

5g和2.4g频段有什么区别

运行的频段不同 2.4G和5G频段的主要区别在于它们运行的频段不同&#xff0c;2.4G频段运行在2.4GHz的频段上&#xff0c;而5G频段&#xff08;这里指的是5GHz频段&#xff09;运行在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…...

地震勘探——干扰波识别、井中地震时距曲线特点

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

CMake 从 GitHub 下载第三方库并使用

有时我们希望直接使用 GitHub 上的开源库,而不想手动下载、编译和安装。 可以利用 CMake 提供的 FetchContent 模块来实现自动下载、构建和链接第三方库。 FetchContent 命令官方文档✅ 示例代码 我们将以 fmt 这个流行的格式化库为例,演示如何: 使用 FetchContent 从 GitH…...

IP如何挑?2025年海外专线IP如何购买?

你花了时间和预算买了IP&#xff0c;结果IP质量不佳&#xff0c;项目效率低下不说&#xff0c;还可能带来莫名的网络问题&#xff0c;是不是太闹心了&#xff1f;尤其是在面对海外专线IP时&#xff0c;到底怎么才能买到适合自己的呢&#xff1f;所以&#xff0c;挑IP绝对是个技…...

【C++】纯虚函数类外可以写实现吗?

1. 答案 先说答案&#xff0c;可以。 2.代码测试 .h头文件 #include <iostream> #include <string>// 抽象基类 class AbstractBase { public:AbstractBase() default;virtual ~AbstractBase() default; // 默认析构函数public:virtual int PureVirtualFunct…...

Docker拉取MySQL后数据库连接失败的解决方案

在使用Docker部署MySQL时&#xff0c;拉取并启动容器后&#xff0c;有时可能会遇到数据库连接失败的问题。这种问题可能由多种原因导致&#xff0c;包括配置错误、网络设置问题、权限问题等。本文将分析可能的原因&#xff0c;并提供解决方案。 一、确认MySQL容器的运行状态 …...

恶补电源:1.电桥

一、元器件的选择 搜索并选择电桥&#xff0c;再multisim中选择FWB&#xff0c;就有各种型号的电桥: 电桥是用来干嘛的呢&#xff1f; 它是一个由四个二极管搭成的“桥梁”形状的电路&#xff0c;用来把交流电&#xff08;AC&#xff09;变成直流电&#xff08;DC&#xff09;。…...

云原生时代的系统设计:架构转型的战略支点

&#x1f4dd;个人主页&#x1f339;&#xff1a;一ge科研小菜鸡-CSDN博客 &#x1f339;&#x1f339;期待您的关注 &#x1f339;&#x1f339; 一、云原生的崛起&#xff1a;技术趋势与现实需求的交汇 随着企业业务的互联网化、全球化、智能化持续加深&#xff0c;传统的 I…...

【threejs】每天一个小案例讲解:创建基本的3D场景

代码仓 GitHub - TiffanyHoo/three_practices: Learning three.js together! 可自行clone&#xff0c;无需安装依赖&#xff0c;直接liver-server运行/直接打开chapter01中的html文件 运行效果图 知识要点 核心三要素 场景&#xff08;Scene&#xff09; 使用 THREE.Scene(…...

【Vue】scoped+组件通信+props校验

【scoped作用及原理】 【作用】 默认写在组件中style的样式会全局生效, 因此很容易造成多个组件之间的样式冲突问题 故而可以给组件加上scoped 属性&#xff0c; 令样式只作用于当前组件的标签 作用&#xff1a;防止不同vue组件样式污染 【原理】 给组件加上scoped 属性后…...

Linux信号保存与处理机制详解

Linux信号的保存与处理涉及多个关键机制&#xff0c;以下是详细的总结&#xff1a; 1. 信号的保存 进程描述符&#xff08;task_struct&#xff09;&#xff1a;每个进程的PCB中包含信号相关信息。 pending信号集&#xff1a;记录已到达但未处理的信号&#xff08;未决信号&a…...