Prime factorization (Sieve)
(Mylib/Number/Prime/prime_factorize_sieve.cpp)

• View this file on GitHub
• Last update: 2021-04-23 23:44:44+09:00

Operations

• PrimeFactorize(int N)
  • p[i] = (iの最小の素因数)
  • Time complexity $O(N log N)$
• factorize(int N)
  • Nの素因数を昇順に列挙する。
  • 素因数の個数だけループが回る。

Requirements

Notes

Problems

References

Code

#pragma once
#include <cstdint>
#include <vector>

namespace haar_lib {
  class prime_factorize_sieve {
    std::vector<int> p_;

  public:
    prime_factorize_sieve() {}
    prime_factorize_sieve(int N) : p_(N + 1) {
      for (int i = 2; i <= N; ++i) {
        if (p_[i] != 0) continue;
        for (int j = i; j <= N; j += i) {
          if (p_[j] == 0) p_[j] = i;
        }
      }
    }

    std::vector<int64_t> factorize(int N) const {
      std::vector<int64_t> ret;

      while (N > 1) {
        ret.push_back(p_[N]);
        N /= p_[N];
      }

      return ret;
    }
  };
}  // namespace haar_lib

#line 2 "Mylib/Number/Prime/prime_factorize_sieve.cpp"
#include <cstdint>
#include <vector>

namespace haar_lib {
  class prime_factorize_sieve {
    std::vector<int> p_;

  public:
    prime_factorize_sieve() {}
    prime_factorize_sieve(int N) : p_(N + 1) {
      for (int i = 2; i <= N; ++i) {
        if (p_[i] != 0) continue;
        for (int j = i; j <= N; j += i) {
          if (p_[j] == 0) p_[j] = i;
        }
      }
    }

    std::vector<int64_t> factorize(int N) const {
      std::vector<int64_t> ret;

      while (N > 1) {
        ret.push_back(p_[N]);
        N /= p_[N];
      }

      return ret;
    }
  };
}  // namespace haar_lib

Back to top page