核心思想
每个合数i×p只会被他最小的质因子p筛一次
代码
for(int i=2;i<=n;i++)
{
if(!v[i]) { v[i]=i,prime[++num]=i; }
//给当前的数i乘一个质因子
for(int j=1;j<=num;j++)
{
if(prime[j]>v[i] || prime[j]>n/i) break ;
v[i*prime[j]]=prime[j];
}
}
每个合数i×p只会被他最小的质因子p筛一次
for(int i=2;i<=n;i++)
{
if(!v[i]) { v[i]=i,prime[++num]=i; }
//给当前的数i乘一个质因子
for(int j=1;j<=num;j++)
{
if(prime[j]>v[i] || prime[j]>n/i) break ;
v[i*prime[j]]=prime[j];
}
}