核心代码分析
void get_prime()
{
for(int i = 2;i <= n;i ++)
{
if(!st[i]) primes[cnt ++] = i;
for(int j = 0;primes[j] * i <= n;j ++)
{
st[primes[j] * i] = true;
if(i % primes[j] == 0) break;
}
}
}
1.
从2开始枚举所有小于n的数,注意i不一定是质数
2.
我们使用st[]数组来标记所有的数是否为质数,在示例代码中st[i] == false时,该数为质数
3.
if(!st[i]) primes[cnt ++] = i;
如果一个数没有被筛掉,那么它一定会是质数,我们将其保存在primes数组中并使计数器cnt++
4.
for(int j = 0;primes[j] * i <= n;j ++)
从第一个我们选中的质数开始枚举,直到primes[j] * i <= n为止,这也是我们每次都能用某个数的最小质因子把它筛掉的原因
5.
st[primes[j] * i] = true;
重点 :如果i % pj == 0,那么代表i的最小质因子是pj,首先我们要明白,根据算术基本定理,任何一个大于1的自然数都可以分解成一系列质数的乘积,那么由于我们从小到大枚举质数,出现在乘积里的这个质因数就一定是最小的。所以pj * i的最小质因子也一定是pj。如果i % primes[j] != 0,同理可知,由于枚举是从小到大的,所以pj一定是pj * i最小的质因子
6.
if(i % primes[j] == 0) break;
为了避免重复筛去某个数,我们只用一个数的最小质因子筛去该数,那么由5可知,此时pj为i的最小质因子,那么我们就应该将其break掉