primetable

int primes[10000010] = {0};//primes[0]计数
int vis[10000010] = {0};
void initprimes(int *primetable,int *visit,int n){
    /*
    *
    *
    * 质数表放到primetable vis是辅助数组,这两个数组至少有n+2的长度且被置0
    *
    *
    *
    欧拉筛法 O(n)造质数表
    在埃氏筛法的基础上，让每个合数只被它的最小质因子筛选一次，以达到不重复的目的。

    对于 i%prime[j] == 0 就break的解释 ：当 i是prime[j]的倍数时，i = kprime[j]，如果继续运算 j+1，i * prime[j+1] = prime[j] * k prime[j+1]，这里prime[j]是最小的素因子，当i = k * prime[j+1]时会重复，所以才跳出循环。举个例子 ：i = 8 ，j = 1，prime[j] = 2，如果不跳出循环，prime[j+1] = 3，8 * 3 = 2 * 4 * 3 = 2 * 12，在i = 12时会计算。因为欧拉筛法的原理便是通过最小素因子来消除。
    对于visit[i*prime[j]] = 1 的解释： 这里不是用i的倍数来消去合数，而是把 prime里面纪录的素数，升序来当做要消去合数的最小素因子。
    原文链接：https://blog.csdn.net/qq_39763472/article/details/82428602
    */
    int i,j;
    for(i = 2;i <= n;i++){
        if(!visit[i]){
            primetable[++primetable[0]] = i;
        }
        for(j = 1;j <= primetable[0] && i * primetable[j] <= n;j++){
            vis[i * primes[j]] = 1;
            if(i % primes[j] == 0)break;
        }
    }
}