埃氏筛、欧拉筛、质因数分解

欧拉筛

$O(n)$

注意欧拉筛从0开始存储

// C++ Version
void init() {
  for (int i = 2; i < MAXN; ++i) {
    if (!vis[i]) {
      pri[cnt++] = i;
    }
    for (int j = 0; j < cnt; ++j) {
      if (1ll * i * pri[j] >= MAXN) break;
      vis[i * pri[j]] = 1;
      if (i % pri[j] == 0) {
        // i % pri[j] == 0
        // 换言之，i 之前被 pri[j] 筛过了
        // 由于 pri 里面质数是从小到大的，所以 i 乘上其他的质数的结果一定也是
        // pri[j] 的倍数 它们都被筛过了，就不需要再筛了，所以这里直接 break
        // 掉就好了
        break;
      }
    }
  }
}

埃氏筛

$O(nloglogn)$

memset(vis, 0, sizeof(vis));//初始化数组，最后数组中为零的就是素数
for (int i = 2; i <= n; i++) {
    for (int j = i * 2; j <= n; j += i) {
        vis[j] = 1;
    }   
}

可进一步优化

$\sqrt{n}loglog\sqrt{n}$

memset(vis, 0, sizeof(vis));
for (int i = 2; i <= sqrt(n); ++i) if (!vis[i]  ) 
    for (int j = i * i; j <= n; j += i) vis[j] = true;

质因数分解

vector<int> breakdown(int N) {
  vector<int> result;
  for (int i = 2; i * i <= N; i++) {
    if (N % i == 0) {  // 如果 i 能够整除 N，说明 i 为 N 的一个质因子。
      while (N % i == 0) N /= i;
      result.push_back(i);
    }
  }
  if (N != 1) {  // 说明再经过操作之后 N 留下了一个素数
    result.push_back(N);
  }
  return result;
}

预处理出从1—MAXN的质因子,时间复杂度nlogn

 for (int i = 2; i < MAXN; i++) {
        if (fac[i].size())continue;
        for (int j = i; j < MAXN; j += i) {
            int t = j, cnt = 0;
            while (t%i == 0)t /= i, cnt++;
            fac[j].push_back({ i,cnt });
        }
}