src/math/eratosthenes.hpp

• View this file on GitHub
• Last update: 2022-12-30 15:03:48+09:00
• Include: #include "src/math/eratosthenes.hpp"

Code

#pragma once

#include <bits/stdc++.h>
using namespace std;

struct Eratosthenes {
private:
  int n;
  vector<bool> is_prime;
  vector<int> minfactor;

public:
  Eratosthenes(int n) : n(n), is_prime(n + 1, true), minfactor(n + 1, -1) {
    is_prime[0] = false;
    is_prime[1] = false;
    minfactor[1] = 1;

    for (int i = 2; i <= n; ++i) {
      if (!is_prime[i]) {
        continue;
      }

      minfactor[i] = i;

      for (int j = i * 2; j <= n; j += i) {
        is_prime[j] = false;

        if (minfactor[j] == -1)
          minfactor[j] = i;
      }
    }
  }

  vector<pair<int, int>> factorize(int i) {
    vector<pair<int, int>> res;
    while (i > 1) {
      int p = minfactor[i];
      int exp = 0;

      while (minfactor[i] == p) {
        i /= p;
        ++exp;
      }
      res.emplace_back(i, exp);
    }
    return res;
  }
};

#line 2 "src/math/eratosthenes.hpp"

#include <bits/stdc++.h>
using namespace std;

struct Eratosthenes {
private:
  int n;
  vector<bool> is_prime;
  vector<int> minfactor;

public:
  Eratosthenes(int n) : n(n), is_prime(n + 1, true), minfactor(n + 1, -1) {
    is_prime[0] = false;
    is_prime[1] = false;
    minfactor[1] = 1;

    for (int i = 2; i <= n; ++i) {
      if (!is_prime[i]) {
        continue;
      }

      minfactor[i] = i;

      for (int j = i * 2; j <= n; j += i) {
        is_prime[j] = false;

        if (minfactor[j] == -1)
          minfactor[j] = i;
      }
    }
  }

  vector<pair<int, int>> factorize(int i) {
    vector<pair<int, int>> res;
    while (i > 1) {
      int p = minfactor[i];
      int exp = 0;

      while (minfactor[i] == p) {
        i /= p;
        ++exp;
      }
      res.emplace_back(i, exp);
    }
    return res;
  }
};

Back to top page