type
status
date
slug
summary
tags
category
icon
password
Property
Mar 4, 2023 02:40 AM
以一个例题引出今天的主角：
AcWing 868. 筛质数
给定一个正整数 ，请你求出 中质数的个数。
输入格式
共一行，包含整数 。
输出格式
共一行，包含一个整数，表示 1∼n1∼n 中质数的个数。
数据范围
1≤n≤1061≤n≤106
输入样例：
8
输出样例：
4
解答：
分析：
时间复杂度：
tips：
- 任何一个合数都可以分解为两数相乘的形式，其中最小的质因子一定是一个质数
- 如果最小因子不是质数，那么一定可以将最小因子继续分解
- 每遇到一个数，都将其与前边的素数乘一遍，即可筛出所有的合数·
- 与线性筛法相比，埃氏筛法的优越点就在于此，线性筛法势必会重复地筛去许多元素，例如
15，在用3和5进行筛选时都会筛一遍
- 为什么不需要写
j<cnt primes数组中存有<=i的所有质数- 当
i是合数时,primes[j]为i的最小质因子时break,j不会越界 - 当
i是质数时,primes数组的最后一个元素就是i, 当primes[j]==i时, break依然不越界
- 当
i % primes[j] == 0时，primes[j]一定是 i 的最小质因子，因此primes[j]一定是primes[j] * i的最小质因子。 当i % primes[j] != 0时，说明i的最小质因子比primes[j]还要大，因此primes[j]一定是primes[j] * i的最小质因子。
- 为什么要在
== 0的时候break掉? 当i是prime[j]的倍数时，有i = k * prime[j]，如果继续运算j+1，i * prime[j+1] = prime[j] * k * prime[j+1]# 这里prime[j]是最小的质因子，当i循环到== k * prime[j+1]时会和i * prime[j+1]重复 # 所以要跳出循环。
- 作者:GJJ
- 链接:https://blog.gaojj.com/article/blog-43
- 声明:本文采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处。