算法板子:质数——判定质数、分解质因数、筛质数

目录

一、判定质数

1. 代码

二、分解质因数

1. 质因数的概念

2. 代码

三、筛质数——获取1~n中所有质数的个数

1. 合数的概念

2. 代码


一、判定质数

1. 代码

#include <iostream>
using namespace std;bool is_prime(int x)
{// 1不是质数, 需要特判if (x == 1) return 0;// i从2枚举到根号xfor (int i = 2; i <= x / i; i ++ )if (x % i == 0) return 0;return 1;
}int main()
{int n;cin >> n;while (n -- ){int a;cin >> a;cout << (is_prime(a) ? "Yes" : "No") << endl;}return 0;
}

二、分解质因数

1. 质因数的概念

 这道题的目的是找到x这个数的质因数的底数和指数。例如280这个数,可以看成2^3 * 5^1 * 7^1,其中2、5和7分别是三个质因数的底数,3、1、1分别是三个质因数的指数。

2. 代码

#include <iostream>
using namespace std;// 假设拆280
void decompose(int x)
{// i从2枚举到根号xfor (int i = 2; i <= x / i; i ++ ){if (x % i == 0){// s代表质数i的个数int s = 0;while (x % i == 0) s ++, x /= i;cout << i << " " << s << endl;}}// 质数x和它的个数1if (x > 1) cout << x << " " << 1 << endl;
}int main()
{int n;cin >> n;while (n -- ){int x;cin >> x;// 拆解xdecompose(x);cout << endl;}return 0;
}

三、筛质数——获取1~n中所有质数的个数

1. 合数的概念

质数和合数是一对相反的概念; 质数是除数只有1和它本身, 合数是除了1和它本身还有别的除数。

2. 代码

#include <iostream>
using namespace std;const int N = 1e6 + 10;// vis[i]代表i这个数是否是合数; vis[4]=1代表4这个数是合数, vis[3]=0代表3这个数不是合数, 是质数
// prime数组记录所有的质数, prime[i]代表第i个质数的值; prime[1]=2代表1~n第一个质数是2
// cnt记录prime数组中质数的个数, 也就是1~n中所有质数的个数
int vis[N], primes[N], cnt;// 获取1~n所有的质数, 存储在prime数组中
void get_primes(int n)
{// 从2开始枚举所有数for (int i = 2; i <= n; i ++ ){// 如果i是质数, 记录下来if (!vis[i]) primes[ ++ cnt] = i;// 不管i是质数还是合数, i*prime[j]一定是合数; i*prime[j]有可能爆int, 把它的结果提升成long longfor (int j = 1; 1LL * i * primes[j] <= n; j ++ ){// 记录i*prime[j]是合数vis[i * primes[j]] = 1;// 如果i是质数, prime[j]就是它本身; 如果i是合数, prime[j]是它的除数中的最小质数if (i % primes[j] == 0) break;}}
}int main()
{int n;cin >> n;// 获取1~n中所有的质数get_primes(n);// 输出1~n中所有质数的个数cout << cnt << endl;return 0;
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/395602.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

QT键盘和鼠标事件

这些事件都在QWidget 中的保护成员方法中 都是虚函数在头文件中声明了 需要类外重现实现 如果头文件中声明 类外无实现就会报错 void Widget::keyPressEvent(QKeyEvent *event) {switch (event->key()) {//获取按键case Qt::Key_W://按键wqDebug()<<"按下w"…

开源免费前端地图开发组件xdh-map

xdh-map是一个基于Openlayers的地图应用Vue组件&#xff0c;具有多方面的功能和特点。以下是对xdh-map的详细介绍&#xff1a; 一、功能与特性 内置多种地图瓦片&#xff1a;xdh-map内置了百度、高德、天地图等地图瓦片&#xff0c;使得开发者可以方便地在应用中集成多种地图…

【Material-UI】Checkbox 组件中的 Label Placement 设置详解

文章目录 一、Checkbox 组件简介1. 组件概述2. labelPlacement 属性 二、labelPlacement 属性的使用方法三、各标签位置的效果与应用场景1. Top&#xff08;顶部&#xff09;2. Start&#xff08;左侧&#xff09;3. Bottom&#xff08;底部&#xff09;4. End&#xff08;右侧…

大模型算力基础设施技术趋势、关键挑战与发展路径

文章目录 前言一、大模型技术发展趋势1.1 大语言模型1.2 多模态模型1.3 长序列模型1.4 混合专家模型二、大模型算力基础设施发展问题与挑战2.1 可用算力规模亟需算力利用效率提升2.2 集群性能提升依赖跨尺度、多层次互联三、大模型算力基础设施高质量发展路径总结前言 从大模型…

使用 `grep` 命令的常用方式

使用 grep 命令的常用方式 grep 是一个强大的命令行工具&#xff0c;用于在文件中搜索文本。无论是程序员、系统管理员还是普通用户&#xff0c;都可以通过 grep 快速定位需要的信息。本文将介绍 grep 命令的一些常用方式&#xff0c;并给出相应示例的执行结果。 示例文本 在…

C语言求平方和倒数

文章目录 1. 代码实现float类型数据double类型数据使用 double 类型的调整 2. 魔数与位级别操作浮点数表示位级别魔数操作 3. 牛顿迭代4. 复杂代码具体解释具体解释&#xff1a;目的&#xff1a;举例&#xff1a; 5.感谢 平方和倒数 广泛用于计算机图形学中&#xff0c;尤其是在…

Spring Boot - 通过ApplicationListener实现接口请求的性能监控

文章目录 概述1. ServletRequestHandledEvent事件2. 实现步骤3. 优缺点分析4. 测试与验证小结其他方案1. 自定义拦截器2. 性能监控平台3. 使用Spring Boot Actuator4. APM工具 概述 在Spring框架中&#xff0c;监控接口请求的性能可以通过ServletRequestHandledEvent事件实现。…

【数据结构】—— 内部排序算法详解

1、前言2、常见排序算法3、排序算法实现3.1 直接插入排序3.2 希尔排序3.3 选择排序3.4 堆排序3.5 冒泡排序3.6 快速排序3.6.1 单趟排序hoare法挖坑法双指针法 3.6.2 非递归实现3.6.3 常见问题基准值的选取小区间优化 3.7 归并排序3.7.1 递归实现3.7.2 非递归实现 3.8 计数排序 …

glibc的安装及MySQL的安全用户角色权限(twenty-one day)

一、glibc安装 mysql 清空/etc/目录下的my.cnf ls -l /etc/my.cnf rm -rf /etc/my.cnf yum -y remove mariadb find / -name "*mysql*" -exec rm -rf {} \; 安装mysql软件包 wget https://downloads.mysql.com/archives/get/p/23/file/mysql-8.0.33-li nux-glibc2.1…

面壁的智能开源 MiniCPM-V 2.6 边缘人工智能多模态功能与 GPT-4V 不相上下

"MiniCPM-V2.6 "是一个边缘多模态人工智能模型&#xff0c;仅拥有 80 亿个参数&#xff0c;却在单图像、多图像和视频理解任务中取得了低于 200 亿个参数的三项 SOTA&#xff08;艺术境界&#xff09;成绩&#xff0c;显著增强了边缘多模态能力&#xff0c;并与 GPT-…

爬虫入门--了解相关工具

目录 1.爬虫与python 2.第一个爬虫 3.web请求的全过程 3.1服务器渲染 3.2前端JS渲染 4.浏览器工具 4.1Elements 4.2Console 4.3Source 4.4network&#xff08;重点&#xff09; 5.小结 1.爬虫与python 首先我们要知道&#xff0c;爬虫一定要用Python么? 非也~…

云计算任务调度优化matlab仿真,对比蚁群优化和蛙跳优化

目录 1.程序功能描述 2.测试软件版本以及运行结果展示 3.核心程序 4.本算法原理 4.1 ACO蚁群优化 4.2 蛙跳优化 5.完整程序 1.程序功能描述 云计算任务调度优化,优化目标位任务消耗时间&#xff0c;调度后的经济效益以及设备功耗&#xff0c;对比蚁群优化算法和蛙跳优化…

三星、小米和 OPPO设备实验室将采用Android设备流技术

早在 5 月份的年度开发者大会上&#xff0c;Google就发布了 Android 设备流测试版。开发人员可以在Google数据中心的真实物理设备上更轻松、更互动地测试自己的应用程序&#xff0c;这些设备会直接串流到 Android Studio。今天&#xff0c;Google宣布与三星、小米和 OPPO 合作扩…

关于LLC知识5

RLC的增益曲线不知一条 频率升高&#xff0c;增益会越来越低 无论在容性区还是感性区&#xff0c;当负载加重的时候&#xff0c;R阻值会变小&#xff0c;所以R的分压也会变小&#xff0c;导致增益会变低 当负载突然加重&#xff0c;输出电压会变低&#xff0c;增益曲线由红色变…

如何让左右两个div各占50%,并且高度相同?

如何设置两个div各占一半&#xff0c;并且高度随着内容增加&#xff0c;而且两边div的高度一致呢&#xff1f;默认会发现高度不一致&#xff0c;改用flex就可以了&#xff0c;另外发现传统的table也可以轻易实现。不知道不用flex的话是否可以实现。 方法1&#xff08;div实现&a…

环境配置:如何在IntelliJ IDEA中安装和修改JDK版本配置(以Windows为例)

环境配置&#xff1a;如何在IntelliJ IDEA中安装和修改JDK版本配置&#xff08;以Windows为例&#xff09; 为了在Java开发中使用最新的功能和优化&#xff0c;升级和配置JDK版本是必不可少的。本文将详细介绍如何下载、安装、配置最新的JDK版本&#xff0c;并在IntelliJ IDEA…

pikachu文件包含漏洞

一&#xff1a;漏洞基础 程序在引用文件的时&#xff0c;引用的文件名存在可控的情况&#xff0c;传入的文件名没有经过合理的校验或校验不严&#xff0c;从而操作了预想之外的文件&#xff0c;就有可能导致文件泄漏和恶意的代码注入&#xff1b; 文件包含漏洞概念 在PHP程序…

安卓将子模块打aar包,并将其远程依赖打包进去

生成 AAR 包 在Android Studio Terminal 窗口输入以下命令&#xff1a; ./gradlew :monitor:assembleRelease把 monitor 换成你子模块的名称&#xff0c;不出意外的话 就会在下面目录生成相应aar文件 注意&#xff1a;如果你的Java运行环境是Java 8 则在老一点的AS上 可以运…

PCIe学习笔记(19)

TLP Prefix&#xff08;前缀&#xff09;规则 以下规则适用于任何包含TLP Prefix的TLP: •对于任何TLP, TLP第0字节的Fmt[2:0]字段值为100b表示存在TLP Prefix, Type[4]位表示TLP Prefix的类型。 ◦Type[4]位的值为0b表示存在Local TLP Prefix ◦Type[4]位的值为1b表示存在…

牛客JS题(二十三)判断质数

注释很详细&#xff0c;直接上代码 涉及知识点&#xff1a; 原型链如何优雅的判断质数 题干&#xff1a; 我的答案 <!DOCTYPE html> <html><head><meta charsetutf-8></head><body><script type"text/javascript">/*** 素…