numtheory/linearSieve.cpp

• View this file on GitHub
• Last update: 2024-07-23 18:02:38+08:00

Code

const int C = 1000001;
vector<int> prime;
int mpf[C];
void sieve() {
  for(int i = 1; i < C; i++)
    mpf[i] = i;
  for(int i = 2; i < C; i++) {
    if (mpf[i] == i)
      prime.emplace_back(i);
    for(int P : prime) {
      if (P > mpf[i] or i * P >= C)
        break;
      mpf[i * P] = P;
    }
  }
}

vector<pii> factorize(int val) {
  vector<pii> res;
  while(val > 1) {
    int p = mpf[val];
    res.emplace_back(p, 0);
    while(val % p == 0)
      res.back().second += 1, val /= p;
  }
  return res;
}

vector<int> factors(int val) {
  vector<int> res(1, 1);
  for(auto [p, idx] : factorize(val)) {
    vector<int> tmp;
    ll base = 1;
    for(int i = 0; i <= idx; i++, base *= p)
      for(int X : res)
        tmp.emplace_back(X * (int)base);
    res.swap(tmp);
  }
  return res;
}

#line 1 "numtheory/linearSieve.cpp"
const int C = 1000001;
vector<int> prime;
int mpf[C];
void sieve() {
  for(int i = 1; i < C; i++)
    mpf[i] = i;
  for(int i = 2; i < C; i++) {
    if (mpf[i] == i)
      prime.emplace_back(i);
    for(int P : prime) {
      if (P > mpf[i] or i * P >= C)
        break;
      mpf[i * P] = P;
    }
  }
}

vector<pii> factorize(int val) {
  vector<pii> res;
  while(val > 1) {
    int p = mpf[val];
    res.emplace_back(p, 0);
    while(val % p == 0)
      res.back().second += 1, val /= p;
  }
  return res;
}

vector<int> factors(int val) {
  vector<int> res(1, 1);
  for(auto [p, idx] : factorize(val)) {
    vector<int> tmp;
    ll base = 1;
    for(int i = 0; i <= idx; i++, base *= p)
      for(int X : res)
        tmp.emplace_back(X * (int)base);
    res.swap(tmp);
  }
  return res;
}

Back to top page