算法随想录

本文记录平时遇到的算法的自然推理过程。

数论算法：#

欧拉筛是对埃氏筛的改进，其目的是解决 合数因拥有多个质因子而被重复筛除 的问题。以下是详细分析：

在埃氏筛中，我们从小到大枚举质数，并将每个质数的若干倍数（通常是自然数的倍数，不包括0和1）标记为合数。质数的定义是 不能被比它小的数（除了1）整除的数，因此，只要将 比当前数小的所有数的倍数筛选出来，我们就可以确定这个数是否为质数。

然而，合数通常可以分解为多个质因子的乘积。例如，，这种情况导致某些合数会被重复标记。这种重复标记的问题出现的原因在于，当我们使用“质数乘以倍数”的筛选模式时，倍数中的最小质因子可能比当前质数还要小，意味着这个数已经在之前被更小的质数标记为合数了，因此，这些倍数不需要再次迭代筛选。

欧拉筛的核心思想是从埃氏筛的 迭代质数倍数 模式转变为 迭代必要的倍数。在埃氏筛中，我们的筛选过程类似如下代码：

for(int i=2; i<n; i++){
    if(primes[i]){
        for(int j=i*i; j<n; j+=i){
            primes[j] = false;
        }
    }
}

如果我们直接按上述逻辑修改埃氏筛，会发现很难判断当前倍数j是否包含比当前质数更小的质因子。而且，对于由 倍数组成的数集 来说，不同质数的筛选本质上并没有区别。因此，我们需要引入一种机制，记录并保存已经筛选过的较小 质数集，并且改变循环顺序，将迭代的倍数作为外层循环，提高效率。

通过这种方法，欧拉筛在减少重复标记合数的同时，大大提高了算法的效率。

来记录背包内最多的价值，状态转移方程为

我的感觉就是分类，找到一个划分之后分情况讨论，就和栈那道题是一样的。你用不同的划分得到的递推都不一样。栈这道题就是 对什么时候pop(1)进行讨论 ，直接就能得到递推式。