对欧拉筛法求素数的重新理解

相信大家在刚开始学习过程中，肯定都会学到，如何判断一个数是不是素数的问题

当时学习到了欧拉筛法，不过其中关键的一步还是没明白，自当背了个板子，现在就重新回来写下

void init() {
    cnt = 0;
    ms(book, true);
    for (int i = 2; i <= M; i++) {
        if (book[i]) {
            num[++cnt] = i;
        }
        for (int j = 1; j <= cnt && (i * num[j] < M); j++) {
            book[num[j] * i] = false;
            if (i % num[j] == 0)break;//重点
        }
    }
    for (int i = 2; i <= cnt; i++) {
        ans[num[i]] = true;
    }
}

其他的都很好理解，关键就是

            if (i % num[j] == 0)break;

　　为什么当 i是num[j]这个素数的倍数的时候就可以停止了呢？

　　首先得明白这句话 ：  任何合数都能表示成多个素数的积。所以，任何的合数肯定有一个最小质因子。我们通过这个最小质因子就可以判断什么时候不用继续筛下去了。

　　当 i%num[j]==0的时候，那么就意味着    num[j]*k==i  （k为整数）

　　所以  i*num[j+1]==X(为任意合数)

　　i*num[j+1]==num[j]*k*num[j+1]==X

　　同时我们也可以知道   i*num[j+1]==num[j]*k*num[j+1]==X ，num[j]才是X的最小质因子。

　　而  num[j+1]>num[j]，所以  num[j+1]*k>num[j]*k

　　可以推出

　　 num[j]*(k*num[j+1])==X==i*num[j+1]

　　意味着  i*num[j+1]必然 “在未来” 会被 num[j]*某个数给筛掉