线性筛

线性筛的核心思路是将质数塞进prime[]集合之中并通过prime集合中的质数去筛掉合数,使用prime集合中此合数的最小
质因子来筛掉此合数。算式 prime[j]<=n/i 的含义其实就是大于n的合数就没必要筛了纯属增加时间复杂度。最让我头疼
的一个代码想了好久终于想通 if(i%prime[j]==0)break; 其实一方面就是为了让每个合数都给最小的质因子筛掉同时也避免
prime[j]数组越界

筛法求欧拉函数

在理解了线性筛的前提下,筛法求欧拉函数的难点主要在于如何求每个合数的欧拉函数,因为质数的欧拉非常好求即除了自身
之外与所有小于它的数互质所以i-1便是质数i的欧拉函数。那么合数的欧拉函数如何求呢?
1:如果 i%prime[j]==0 那么prime[j]一定是i的最小质因子,否则早就break了轮不到当前的prime[j],所以prime[j]一定是
i的最小质因子,同样 i×prime[j] 的最小质因子也一定是 prime[j] ,因为i一定>=prime[j],i×prime[j]其实只是在i的基
础上乘上了一个prime[j],然而这个prime[j]同样出现在i中,所以i和pirme[j]×i的phi都要乘上(1-1/prime[j])其他的质因
子是共有的当然一视同仁,曲线救国思想i和i×prime[j]同时乘上一类数那么比值当然不变所以这处可以简写为：
phi[i×prime[j]]=phi[i]×prime[j]其实只是N比之前大了prime[j]倍罢了
2：i%prime[j]!=0其实想通了1式就显得很简单了,因为i中没有prime[j]的质因子,而prime[j]×i中有此质因子那么i不用乘
而prime[j]×i还要乘上一个1-1/prime[j],也就变成了phi[i×prime[j]]=phi[i]×prime[j]×(1-1/prime[j])<==>phi[i]×
(prime[j]-1)
综上便是筛法求欧拉的核心思想,公式的推导。