欧拉筛
bool isprime[MAXN]; // isprime[i]表示i是不是素数 int prime[MAXN]; // 现在已经筛出的素数列表 int n; // 上限,即筛出<=n的素数 int cnt; // 已经筛出的素数个数 void euler() { memset(isprime, true, sizeof(isprime)); // 先全部标记为素数 isprime[1] = false; // 1不是素数 for(int i = 2; i <= n; ++i) // i从2循环到n(外层循环) { if(isprime[i]) prime[++cnt] = i; // 如果i没有被前面的数筛掉,则i是素数 for(int j = 1; j <= cnt && i * prime[j] <= n; ++j) // 筛掉i的素数倍,即i的prime[j]倍 // j循环枚举现在已经筛出的素数(内层循环) { isprime[i * prime[j]] = false; // 倍数标记为合数,也就是i用prime[j]把i * prime[j]筛掉了 if(i % prime[j] == 0) break; // 最神奇的一句话,如果i整除prime[j],退出循环 // 这样可以保证线性的时间复杂度 } } }
标签:int,筛出,素数,MAXN,isprime,欧拉 From: https://www.cnblogs.com/mingzhaomz/p/17976678