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

质数(埃氏筛、欧拉筛)

小赛码/数论

竞赛/数论

质数

一、质数:数字的原子

  • 原子是构成物质的基本单位

  • 质数是构建整数的基本单元

示例
60 = 2 × 2 × 3 × 5(仅由质数构成)
所有大于1的自然数都可分解为质数的乘积

类比说明

质数如同数学界的乐高积木,通过组合可构建任意整数


二、质数:现代密码的基石(RSA加密)

  • 保护移动支付、即时通讯、数据传输的核心技术

  • RSA加密原理

    基于大质数乘积的数学特性:正向计算易,逆向分解难


三、质数的分布特性

前20个质数序列:
2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71...

分布规律:

  1. 密度递减:数字越大,质数出现频率越低

  2. 间距不规则:存在紧密对(如11-13)和巨大间隔(如113-127)

研究思考题

为何质数分布不遵循简单规律?
能否建立有效的质数预测模型?(尚未解决)


RSA加密算法详解

一、核心机制

通过三个关键步骤实现信息安全:

步骤 操作 数学基础
密钥生成 选择两个超大质数p,q 质数无限性
加密过程 计算n=p×q及公钥 大数分解困难
解密过程 使用私钥还原信息 欧拉函数特性

安全核心

当 n 超过 300 位时,暴力分解需数亿年计算时间

一、RSA 算法原理详解

1. 密钥生成步骤

第一步:选择两个不同的大质数

p = 61
q = 53

第二步:计算模数n和欧拉函数值φ(n)

n = p × q = 61 × 53 = 3233
φ(n) = (p-1)×(q-1) = 60 × 52 = 3120
  • n作为公钥的一部分公开
  • φ(n)用于后续密钥计算

第三步:选择公钥指数e

e = 17  (需满足1 < e < φ(n)且gcd(e, φ(n))=1)

第四步:计算私钥指数d


d ≡ e⁻¹ mod φ(n)
通过扩展欧几里得算法求得d = 2753
∵ 17 × 2753 = 46801 ≡ 1 mod 3120

2. 加密解密过程演示

加密消息m=65

c = m^e mod n = 65¹⁷ mod 3233 = 2790

解密过程

m = c^d mod n = 2790²⁷⁵³ mod 3233 = 65

二、质数判定算法

1. 试除法(朴素方法)

算法原理:

  • 质数定义:大于1的自然数,除了1和它本身外没有其他约数

  • 优化:只需检查2到√n之间的整数

C++实现:


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

时间复杂度分析:

  • 单个数:O(√n)

  • 前N个数:O(N√N)

2. 埃拉托斯特尼筛法

算法步骤:

  1. 初始化布尔数组标记所有数为质数

  2. 从2开始,标记其倍数为合数

  3. 重复直到√n

C++实现:

void sieveOfEratosthenes(int n) {vector<bool> is_prime(n+1, true);is_prime[0] = is_prime[1] = false;for (int i = 2; i * i <= n; ++i) {if (is_prime[i]) {for (int j = i * i; j <= n; j += i)is_prime[j] = false;}}
}

时间复杂度:
O(n log log n)

3. 欧拉线性筛法

算法优势:

  • 每个合数只被标记一次

  • 可记录最小质因子

C++实现:

void linearSieve(int n) {vector<int> primes;vector<bool> is_prime(n+1, true);for (int i = 2; i <= n; ++i) {if (is_prime[i]) {primes.push_back(i);}for (int p : primes) {if (i * p > n) break;is_prime[i * p] = false;if (i % p == 0) break;}}
}

时间复杂度:
O(n)

教学流程

步骤 内容 形式
1 朴素枚举法 手动判断10以内质数
2 埃氏筛图解 小圆点图示(划掉倍数)
3 编写埃氏筛代码 强调 j=i*i 优化
4 时间复杂度分析 提问:哪些数字被重复处理?
5 线性筛原理 "最小质因子唯一性"示例
6 效率对比 10万级质数生成速度实测
http://www.hskmm.com/?act=detail&tid=15915

相关文章:

  • HarmonyOS数据持久化:Preferences轻量级存储实战
  • HarmonyOS服务卡片开发:动态卡片与数据绑定实战指南
  • 有理数类的问题回答
  • HarmonyOS后台任务调度:JobScheduler与WorkManager实战指南
  • 总线传输的四个阶段
  • HarmonyOS事件订阅与通知:后台事件处理
  • HarmonyOS后台任务管理:短时与长时任务实战指南
  • Kali Linux 2025.3 发布 (Vagrant Nexmon) - 领先的渗透测试发行版
  • C语言多线程同步详解:从互斥锁到条件变量
  • Browser Use调用浏览器入门
  • 安防视频监控新时代:国标GB28181平台EasyGBS的可视化首页如何重塑运维与管理体验?
  • LazyForEach性能优化:解决长列表卡顿问题
  • java函数式编程的学习01
  • Manim实现镜面反射特效
  • 25Java基础之IO(二)
  • 【P2860】[USACO06JAN] Redundant Paths G - Harvey
  • GUI软件构造
  • 企业微信客服API模式接入第三方客服系统,对接大模型AI智能体
  • react使用ctx和reducer代替redux
  • KM 乱记
  • 深入解析:B树与B+树的原理区别应用
  • linux中的服务监控,停用自动重启
  • RHEL7/CentOS7 install NVIDIA drivers and CUDA
  • 浅谈 Burnside 和 Polya 的证明
  • 算法学习笔记:支配对
  • 西电PCB设计指南第5章学习笔记
  • ImageMagick - 关于图片压缩,通过dk整理的一些可用指令 - window64
  • 【杂记】原 hack
  • 全新升级!EasyDSS会议管理3大核心功能,让远程协作更高效
  • 黄金、原油期货数据API对接文档