AcWing 868. 筛质数

输入格式

输出格式

数据范围

1≤n≤1061≤n≤106

输入样例：

8

输出样例：

4

解答：

分析：

tips：

1. 任何一个合数都可以分解为两数相乘的形式，其中最小的质因子一定是一个质数
• 如果最小因子不是质数，那么一定可以将最小因子继续分解

2. 每遇到一个数，都将其与前边的素数乘一遍，即可筛出所有的合数·
• 与线性筛法相比，埃氏筛法的优越点就在于此，线性筛法势必会重复地筛去许多元素，例如15，在用3和5进行筛选时都会筛一遍

3. 为什么不需要写j<cnt
• primes数组中存有<=i的所有质数
• 当i是合数时, primes[j]为i的最小质因子时break, j不会越界
• 当i是质数时, primes数组的最后一个元素就是i, 当primes[j]==i时, break依然不越界

4. 当 i % primes[j] == 0 时，primes[j] 一定是 i 的最小质因子，因此 primes[j] 一定是 primes[j] * i 的最小质因子。 当 i % primes[j] != 0 时，说明i的最小质因子比primes[j]还要大，因此 primes[j] 一定是 primes[j] * i 的最小质因子。

5. 为什么要在 == 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] 重复 # 所以要跳出循环。