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

质数(判定质数 分解质因数 筛质数)

目录

  • 一、判定质数
    • 思路分析
    • 代码实现
  • 二、分解质因数
    • 思路分析
    • 典型题目
    • 代码实现
  • 三、质数筛
    • 经典题目
    • 思路分析
      • 1. 朴素筛法
      • 2. 埃氏筛法
      • 3. 欧拉筛法


一、判定质数

思路分析

由于每个合数的因子是成对出现的,即如果 d d d n n n 的因子,那么 n d \frac{n}{d} dn 也是 n n n 的因子,故从 1 1 1 n n n 的枚举可以缩减到 1 1 1 n \sqrt{n} n ,即让 d ≤ n d d \leq \frac{n}{d} ddn,从而得到 d ≤ n d \leq \sqrt{n} dn


代码实现

bool is_prime(int n)
{if (n < 2) return false;for (int i = 2; i <= n / i; ++i){if (n % i == 0) return false;}return true;
}

时间复杂度: O ( n ) O(\sqrt{n}) O(n )


二、分解质因数

思路分析

每个合数都是由质数相乘得到的。合数可以写成质因数的乘积,这是数论中的一个基本命题。

例如:
12 = 2 * 2 * 3
18 = 2 * 3 * 3
24 = 2 * 2 * 2 * 3

① 对于任何一个合数 n n n,在它的质因数分解中,至多有一个质因子大于 n \sqrt{n} n

② 同时也可以推出,对任何一个合数 n n n,在它的质因数分解中,至少会有一个质因子小于或等于 n \sqrt{n} n


典型题目

题目描述:
给定 n n n 个正整数 a i a_i ai,将每个数分解质因数,并按照质因数从小到大的顺序输出每个质因数的底数和指数。

输入格式:
第一行包含整数 n n n

接下来 n n n 行,每行包含一个正整数 a i a_i ai

输出格式:
对于每个正整数 a i a_i ai,按照从小到大的顺序输出其分解质因数后,每个质因数的底数和指数,每个底数和指数占一行。

每个正整数的质因数全部输出完毕后,输出一个空行。

数据范围:
1 ≤ n ≤ 100 , 2 ≤ a i ≤ 2 ∗ 1 0 9 1≤n≤100,2≤a_i≤2*10^9 1n100,2ai2109

输入样例:

2
6
8

输出样例:

2 1
3 12 3

代码实现

#define _CRT_NO_SECURE_WARNINGS
#include<iostream>using namespace std;void divide(int x)
{for (int i = 2; i <= x / i; ++i) // 遍历出所有小于或等于sqrt(n)的质因子{if (x % i == 0){int cnt = 0;while (x % i == 0){cnt++;x /= i;}cout << i << ' ' << cnt << endl;}}// 输出大于sqrt(n)的质因子或是质数本身if (x > 1) cout << x << ' ' << 1 << endl;cout << endl;
}
int main()
{int n;cin >> n;while (n--){int x;cin >> x;divide(x);}return 0;
}

时间复杂度:在 O ( log ⁡ n ) O(\log n) O(logn) O ( n ) O(\sqrt n) O(n )之间
解释:若 n n n 2 2 2 的倍数,时间复杂度将会变为 O ( log ⁡ n ) O(\log n) O(logn)


三、质数筛

经典题目

题目描述:
给定一个正整数 n n n,请你求出 1 ∼ n 1∼n 1n 中质数的个数。

输入格式:
共一行,包含整数 n n n

输出格式:
共一行,包含一个整数,表示 1 ∼ n 1∼n 1n 中质数的个数。

数据范围:
1 ≤ n ≤ 1 0 6 1≤n≤10^6 1n106

输入样例:

8

输出样例:

4

思路分析

在这里插入图片描述
通过将素数的倍数筛掉的方法,剩余存留的则全为质数。

筛完后 P P P 2 2 2 ~ ( P − 1 P-1 P1) 之间不存在倍数关系,即 P P P 无质因子在 2 2 2 ~ ( P − 1 P-1 P1) 之间。


1. 朴素筛法

通过将2~n的所有数的倍数筛掉的方法来得到范围内所有的质数

#define _CRT_NO_SECURE_WARNINGS
#include<iostream>using namespace std;const int N = 1e6 + 10;
int prime[N], cnt;
bool st[N];void get_prime(int n)
{for (int i = 2; i <= n; ++i){if (!st[i]){prime[cnt++] = i;}for (int j = 2 * i; j <= n; j += i) st[j] = true; // 将2~n所有数的倍数都打上标记}
}
int main()
{int n;cin >> n;get_prime(n);cout << cnt << endl;return 0;
}

时间复杂度: O ( n log ⁡ n ) O(n \log n) O(nlogn)

n 2 + n 3 + n 4 + . . . + + n n = n ( 1 2 + 1 3 + 1 4 + . . . + 1 n ) \frac{n}{2} + \frac{n}{3} + \frac{n}{4} + ... + + \frac{n}{n} = n(\frac{1}{2} + \frac{1}{3} + \frac{1}{4} + ... + \frac{1}{n}) 2n+3n+4n+...++nn=n(21+31+41+...+n1)

调和级数: lim ⁡ n → ∞ ( 1 2 + 1 3 + 1 4 + . . . + 1 n ) = ln ⁡ n + c \lim_{n \to \infty} (\frac{1}{2} + \frac{1}{3} + \frac{1}{4} + ... + \frac{1}{n}) = \ln n + c limn(21+31+41+...+n1)=lnn+c (欧拉常数 c = 0.577 c = 0.577 c=0.577)

因此可得时间复杂度为 O ( n log ⁡ n ) O(n \log n) O(nlogn)


2. 埃氏筛法

优化了朴素筛法,只将2~n的质数的倍数筛掉的方法来得到范围内所有的质数

#define _CRT_NO_SECURE_WARNINGS
#include<iostream>using namespace std;const int N = 1e6 + 10;
int prime[N], cnt;
bool st[N];void get_prime(int n)
{for (int i = 2; i <= n; ++i){if (st[i]) continue;prime[cnt++] = i;for (int j = 2 * i; j <= n; j += i) st[j] = true; // 将2~n所有质数的倍数都打上标记}
}
int main()
{int n;cin >> n;get_prime(n);cout << cnt << endl;return 0;
}

时间复杂度为 O ( n log ⁡ log ⁡ n ) O(n \log \log n) O(nloglogn)

质数定理:在 1 1 1 n n n 之间的质数个数约等于 n ln ⁡ n \frac{n}{\ln n} lnnn


3. 欧拉筛法

核心思想:在埃氏筛法的基础上,让每个合数只被它的最小质因子筛选一次,以达到不重复的目的。

步骤:

  • i = 2 i = 2 i=2 开始,如果 i i i 还没有被筛掉,则将 i i i 加入至素数列表中。
  • 遍历当前素数列表 p r i m e [ ] prime[] prime[],筛去 i ∗ p r i m e [ j ] i ∗ prime[j] iprime[j]
    (保证 p r i m e [ j ] ∗ i prime[j] ∗ i prime[j]i 不能越界,因为越界了对结果没意义。即 i ∗ p r i m e [ j ] ≤ n i ∗ prime[j] \leq n iprime[j]n
  • 当遍历到能整除 i 的素数 p r i m e [ j ] prime[j] prime[j] 时,筛去 i ∗ p r i m e [ j ] i ∗ prime[j] iprime[j],停止对素数列表的遍历。
  • 重复 2 , 3 , 4 2,3,4 2,3,4,直到所有不超过 n n n 的整数都被遍历过素数列表中的元素即为所求的不超过 n n n 的所有素数。
#define _CRT_NO_SECURE_WARNINGS
#include<iostream>using namespace std;const int N = 1e6 + 10;
int cnt, prime[N];
bool st[N];void get_prime(int n)
{for (int i = 2; i <= n; ++i){if (!st[i]) prime[cnt++] = i;for (int j = 0; prime[j] <= n / i; j++){st[prime[j] * i] = true;if (i % prime[j] == 0) break; // 只被它的最小质因子筛选一次}}
}
int main()
{int n;cin >> n;get_prime(n);cout << cnt << endl;return 0;
}

n < 1 0 6 n<10^6 n<106,欧拉筛和埃氏筛所花费的时间差不多;但是若 n > 1 0 7 n>10^7 n>107,欧拉筛会比埃氏筛快了大概一倍。

相关文章:

质数(判定质数 分解质因数 筛质数)

目录 一、判定质数思路分析代码实现 二、分解质因数思路分析典型题目代码实现 三、质数筛经典题目思路分析1. 朴素筛法2. 埃氏筛法3. 欧拉筛法 一、判定质数 思路分析 由于每个合数的因子是成对出现的&#xff0c;即如果 d d d 是 n n n 的因子&#xff0c;那么 n d \frac…...

SAP数据库表维护视图生成器的使用

在SAP中&#xff0c;经常需要自定义数据库表。而且可能需要人工维护数据库表中的数据&#xff0c;可以通过SM30进行维护数据&#xff1b;但是SM30事务的权限太大&#xff0c;不适宜将SM30直接分配&#xff1b;因此&#xff0c;可以通过给维护表分配事务代码&#xff0c;来达到控…...

数据结构 | 递归

目录 一、何谓递归 1.1 计算一列数之和 1.2 递归三原则 1.3 将整数转换成任意进制的字符串 二、栈帧&#xff1a;实现递归 三、递归可视化 四、谢尔平斯基三角形 五、复杂的递归问题 六、动态规划 一、何谓递归 递归是解决问题的一种办法&#xff0c;它将问题不断地分…...

微信发视频怎么不压缩画质?试试这几招

微信是我们常用的社交工具了&#xff0c;很多朋友都会用它跟好友分享视频&#xff0c;但想必大家都知道&#xff0c;微信为了节省宽带和存储空间&#xff0c;会自动对上传的视频进行压缩处理&#xff0c;甚至过大的视频会被限制发送&#xff0c;怎么才能让微信不自动压缩画质呢…...

【网络安全带你练爬虫-100练】第16练:使用session发送请求

目录 一、目标1&#xff1a;使用seesion进去请求 二、网络安全O 一、目标1&#xff1a;使用seesion进去请求 &#xff08;1&#xff09;应用&#xff1a; 通过创建会话&#xff08;session&#xff09;对象来请求并爬取返回的数据包 情景&#xff1a;需要登录才能爬取的网…...

论文代码学习—HiFi-GAN(3)——模型损失函数loss解析

文章目录 引言正文生成器损失函数最小二乘损失函数梅尔频谱图损失函数特征匹配损失函数生成器最终损失函数loss生成器loss对应代码 鉴定器损失函数鉴定器损失函数代码 总结引用 引言 这里翻译了HiFi-GAN这篇论文的具体内容&#xff0c;具体链接。这篇文章还是学到了很多东西&a…...

CLion中avcodec_receive_frame()问题

1. 介绍 在提取音视频文件中音频的PCM数据时&#xff0c;使用avcodec_receive_frame()函数进行解码时&#xff0c;遇到了一些问题&#xff0c;代码在Visual Studio 2022中运行结果符合预期&#xff0c;但是在CLion中运行时&#xff0c;获取的AVFrame有错误&#xff0c;和VS中获…...

Linux安装操作(Mac版本)

Parallels Desktop的简介 Parallels Desktop是Mac平台上的虚拟机软件&#xff0c;也是Mac平台最好的虚拟机软件之一。它允许用户在Mac OS X系统上同时运行其他操作系统&#xff0c;例如Windows、Linux等。Parallels Desktop为Mac用户提供了使用其他操作系统和软件的便利性&…...

Linux(四)--包软件管理器与Linux上软件的下载示例

一.包软件管理器【yum和apt】 1.先来学习使用yum命令。yum&#xff1a;RPM包软件管理器&#xff0c;用于自动化安装配置Linux软件&#xff0c;并可以自动解决依赖问题。通过yum命令我们可以轻松实现软件的下载&#xff0c;查找&#xff0c;卸载与更新等管理软件的操作。 最常用…...

HTML <param> 标签

实例 向 HTML 代码添加一个对象: <object classid="clsid:F08DF954-8592-11D1-B16A-00C0F0283628" id="Slider1" width="100" height="50"><param name="BorderStyle" value="1" /><param nam…...

基于ARM+FPGA (STM32+ Cyclone 4)的滚动轴承状态监测系统

状态监测系统能够在故障早期及时发现机械设备的异常状态&#xff0c;避免故障的 进一步恶化造成不必要的损失&#xff0c;滚动轴承是机械设备的易损部件&#xff0c;本文对以滚动 轴承为研究对象的状态监测系统展开研究。现有的监测技术多采用定时上传监 测数据&#xff0c;…...

二、数据结构10:堆 模板题+算法模板(堆排序,模拟堆)

文章目录 算法模板堆题目代码模板堆的原理down操作理解&#xff1a;up操作理解建堆操作关于heap_swap中存的映射数组理解&#xff08;模拟堆题目中用到&#xff09; 模板题堆排序原题链接题目思路题解 模拟堆原题链接题目思路题解 算法模板 堆题目代码模板 // h[N]存储堆中的…...

W6100-EVB-PICO做DNS Client进行域名解析

前言 在上一章节中我们用W6100-EVB-PICO通过dhcp获取ip地址&#xff08;网关&#xff0c;子网掩码&#xff0c;dns服务器&#xff09;等信息&#xff0c;给我们的开发板配置网络信息&#xff0c;成功的接入网络中&#xff0c;那么本章将教大家如何让我们的开发板进行DNS域名解…...

【linux-网络】4层转发方法-iptable以及nginx

1.背景 有时候远程或者某些业务需要做转发就会用到iptables或者nginx&#xff0c;或者ss都可以 根据自己的情况去适配。 2.方法&#xff1a; 1&#xff09;iptables -把linux内核转发功能打开 echo "net.ipv4.ip_forward1" >> /etc/sysctl.conf -出入转发…...

vue复制文案,复制图片,黏贴图片

vue 实现复制文案&#xff0c;复制图片&#xff0c;在微信聊天框&#xff0c;黏贴为图片 //安装 cnpm i clipboard-all //引用 import clipboard from clipboard-all<!-- row.url 图片路径 --><div ref"foo" class"hidden"><img :src"…...

Web应急思路

Web应急思路 找到webshell --> 确定攻击者IP --> 回溯攻击者操作 --> 梳理整个攻击过程 1.寻找webshell方法 1.文件内容中的恶意函数 2.web日志中的webshell特征 3.贴合web业务中的URL来分析web日志 4.源码版本管理对比&#xff0c;注重修改或新增的脚本文件 5.统计…...

shell脚本清理redis模糊匹配的多个key,并计算释放内存大小

#!/bin/bash# 定义Redis服务器地址和端口 REDIS_HOST"localhost" REDIS_PORT6380# 获取Redis当前内存使用量&#xff08;以字节为单位&#xff09; function get_redis_memory_usage() {redis-cli -h $REDIS_HOST -p $REDIS_PORT INFO memory | grep "used_memo…...

python-MySQL数据库建表语句(需要连接数据库)转存为Excel文档-工作小记

将create table XXXXXX 转为指定Excel文档。该脚本适用于数据库表结构本地文档记录 呈现效果 代码 # -*- coding:utf-8 -*- # Time : 2023/8/2 15:14 # Author: 水兵没月 # File : MySQL建表_2_excel.py import reimport mysql.connector import pandas as pd db 库名 mydb …...

iOS Block介绍

文章目录 一、Block定义二、block为什么用copy修饰三、block使用时的注意事项四、使用 block时什么情况会发生引用循环&#xff0c;如何解决&#xff1f;五、在block内如何修改block外部变量&#xff1f;六、__block与__weak的区别 一、Block定义 目的就是能够直接存储一个代码…...

小程序安全性加固:如何保护用户数据和防止恶意攻击

第一章&#xff1a;引言 在当今数字化时代&#xff0c;移动应用程序的使用已经成为人们日常生活中的重要组成部分。小程序作为一种轻量级的应用程序形式&#xff0c;受到了广泛的欢迎。然而&#xff0c;随着小程序的流行&#xff0c;安全性问题也日益凸显。用户数据泄露和恶意攻…...

变量 varablie 声明- Rust 变量 let mut 声明与 C/C++ 变量声明对比分析

一、变量声明设计&#xff1a;let 与 mut 的哲学解析 Rust 采用 let 声明变量并通过 mut 显式标记可变性&#xff0c;这种设计体现了语言的核心哲学。以下是深度解析&#xff1a; 1.1 设计理念剖析 安全优先原则&#xff1a;默认不可变强制开发者明确声明意图 let x 5; …...

深度学习在微纳光子学中的应用

深度学习在微纳光子学中的主要应用方向 深度学习与微纳光子学的结合主要集中在以下几个方向&#xff1a; 逆向设计 通过神经网络快速预测微纳结构的光学响应&#xff0c;替代传统耗时的数值模拟方法。例如设计超表面、光子晶体等结构。 特征提取与优化 从复杂的光学数据中自…...

linux之kylin系统nginx的安装

一、nginx的作用 1.可做高性能的web服务器 直接处理静态资源&#xff08;HTML/CSS/图片等&#xff09;&#xff0c;响应速度远超传统服务器类似apache支持高并发连接 2.反向代理服务器 隐藏后端服务器IP地址&#xff0c;提高安全性 3.负载均衡服务器 支持多种策略分发流量…...

智慧医疗能源事业线深度画像分析(上)

引言 医疗行业作为现代社会的关键基础设施,其能源消耗与环境影响正日益受到关注。随着全球"双碳"目标的推进和可持续发展理念的深入,智慧医疗能源事业线应运而生,致力于通过创新技术与管理方案,重构医疗领域的能源使用模式。这一事业线融合了能源管理、可持续发…...

Java 8 Stream API 入门到实践详解

一、告别 for 循环&#xff01; 传统痛点&#xff1a; Java 8 之前&#xff0c;集合操作离不开冗长的 for 循环和匿名类。例如&#xff0c;过滤列表中的偶数&#xff1a; List<Integer> list Arrays.asList(1, 2, 3, 4, 5); List<Integer> evens new ArrayList…...

Cloudflare 从 Nginx 到 Pingora:性能、效率与安全的全面升级

在互联网的快速发展中&#xff0c;高性能、高效率和高安全性的网络服务成为了各大互联网基础设施提供商的核心追求。Cloudflare 作为全球领先的互联网安全和基础设施公司&#xff0c;近期做出了一个重大技术决策&#xff1a;弃用长期使用的 Nginx&#xff0c;转而采用其内部开发…...

自然语言处理——Transformer

自然语言处理——Transformer 自注意力机制多头注意力机制Transformer 虽然循环神经网络可以对具有序列特性的数据非常有效&#xff0c;它能挖掘数据中的时序信息以及语义信息&#xff0c;但是它有一个很大的缺陷——很难并行化。 我们可以考虑用CNN来替代RNN&#xff0c;但是…...

Map相关知识

数据结构 二叉树 二叉树&#xff0c;顾名思义&#xff0c;每个节点最多有两个“叉”&#xff0c;也就是两个子节点&#xff0c;分别是左子 节点和右子节点。不过&#xff0c;二叉树并不要求每个节点都有两个子节点&#xff0c;有的节点只 有左子节点&#xff0c;有的节点只有…...

华硕a豆14 Air香氛版,美学与科技的馨香融合

在快节奏的现代生活中&#xff0c;我们渴望一个能激发创想、愉悦感官的工作与生活伙伴&#xff0c;它不仅是冰冷的科技工具&#xff0c;更能触动我们内心深处的细腻情感。正是在这样的期许下&#xff0c;华硕a豆14 Air香氛版翩然而至&#xff0c;它以一种前所未有的方式&#x…...

Go 语言并发编程基础:无缓冲与有缓冲通道

在上一章节中&#xff0c;我们了解了 Channel 的基本用法。本章将重点分析 Go 中通道的两种类型 —— 无缓冲通道与有缓冲通道&#xff0c;它们在并发编程中各具特点和应用场景。 一、通道的基本分类 类型定义形式特点无缓冲通道make(chan T)发送和接收都必须准备好&#xff0…...