LPF Table
(math/lpf-table.hpp)

• View this file on GitHub
• Last update: 2025-10-21 21:13:36+09:00
• Include: #include "math/lpf-table.hpp"

Required by

• Power Table (modint/power-table.hpp)

Verified with

• verify/fps/LC_sum_of_exponential_times_polynomial.test.cpp
• verify/fps/LC_sum_of_exponential_times_polynomial_limit.test.cpp

Code

#pragma once

vector<int> LPFTable(int n) {
  vector<int> lpf(n + 1, 0);
  iota(lpf.begin(), lpf.end(), 0);
  for (int p = 2; p * p <= n; p += (p & 1) + 1) {
    if (lpf[p] != p) continue;
    for (int i = p * p; i <= n; i += p)
      if (lpf[i] == i) lpf[i] = p;
  }
  return lpf;
}
/**
 * @brief LPF Table
 */

#line 2 "math/lpf-table.hpp"

vector<int> LPFTable(int n) {
  vector<int> lpf(n + 1, 0);
  iota(lpf.begin(), lpf.end(), 0);
  for (int p = 2; p * p <= n; p += (p & 1) + 1) {
    if (lpf[p] != p) continue;
    for (int i = p * p; i <= n; i += p)
      if (lpf[i] == i) lpf[i] = p;
  }
  return lpf;
}
/**
 * @brief LPF Table
 */

Back to top page