1.核心代码

    int cnt = 0;
    for(int i = 2; i <= n; i ++){
        if(!st[i]) primes[cnt ++] = i;
        for(int j = 0; primes[j] <= n/i; j ++) {
            st[primes[j] * i] = true;
            if(i % primes[j]) break;
        }
    }
    return cnt;

2.题解

线性筛法本质上就是用最小的质因子对合数进行筛选

首先理解primes[j] * i:
假设对任何合数t，i为t的最大因子，根据t = i * p 则p一定是质数
第一层循环实际上遍历的就是i,用来填质数数组;
而真正筛选的部分在第二层循环——遍历质数数组primes中的i的时候:

举个例子模拟一下:
12的因子: {2, 3, 4, 6}

二层循环最开始筛选的时候是for(int j = 0; primes[j] * i <= n; j++)———是从零开始遍历质数数组的
i = 6: 当遍历质数数组的第一个元素2时: st[2 * 6] = true就把12筛掉了; 而且这个时候primes数组中 {2, 3, 5}。