1.算法本身是基于某个原理设计的,所以增加了阅读的难度,如果你想单纯看代码基本看不懂,因为代码就是把这种原理实现了一遍。
2.void get_primes(int n)
{
for (int i = 2; i <= n; i ++ )
{
if (!st[i]) primes[cnt ++ ] = i;//(1)此时已经把数筛完可以判断是否放入primes中
for (int j = 0; primes[j] <= n / i; j ++ )(2)for循环保证不会越界
{
st[primes[j] * i]=true;(3)根据公式原理针对当前i,筛掉几个质数,个数就是当前i的最小质因子之前的几个,比如当前i=5,5之前有2,3,5三个质数存在primes中(5之所以也存在是因为之前没有被筛掉),就将10,15,25筛掉,
if (i % primes[j] == 0) break;(4)假如当前i=12,最小质因子为2,因此可以筛掉24,但是此时不停
枚举primes[j]=3,会在此时筛掉36,但是36应该被2筛掉,而不是3,所以在i=18的时候就会从新筛掉一遍!
为保证每次只筛掉i与最小质因子的乘积,所以需要break!
}
}
}
(2)