prime/prime-enumerate.hpp

• View this file on GitHub
• Last update: 2020-12-05 08:35:39+09:00
• Include: #include "prime/prime-enumerate.hpp"

Required by

• 無平方数の数え上げ (multiplicative-function/count-square-free.hpp)
• 倍数変換・約数変換 (multiplicative-function/divisor-multiple-transform.hpp)
• 乗法的関数の列挙 (multiplicative-function/enamurate-multiplicative-function.hpp)
• GCD畳み込み (multiplicative-function/gcd-convolution.hpp)
• 有名な乗法的関数 (multiplicative-function/mf-famous-series.hpp)
• 素数カウント( $\mathrm{O}(N^{\frac{2}{3}})$ ) (multiplicative-function/prime-counting-o2d3.hpp)
• 乗法的関数のprefix sum (multiplicative-function/sum-of-multiplicative-function.hpp)

Verified with

• verify/verify-unit-test/garner-bigint.test.cpp
• verify/verify-unit-test/mf.test.cpp
• verify/verify-unit-test/multiplicative-function.test.cpp
• verify/verify-unit-test/primitive-root.test.cpp
• verify/verify-unit-test/sum-of-mf.test.cpp
• verify/verify-yosupo-math/yosupo-count-squarefrees.test.cpp
• verify/verify-yosupo-math/yosupo-counting-primes-2.test.cpp
• verify/verify-yosupo-math/yosupo-gcd-convolution.test.cpp
• verify/verify-yosupo-math/yosupo-lcm-convolution.test.cpp
• verify/verify-yosupo-math/yosupo-prime-table.test.cpp
• verify/verify-yosupo-math/yosupo-sum-of-totient-2.test.cpp
• verify/verify-yuki/yuki-0125.test.cpp
• verify/verify-yuki/yuki-0886.test.cpp
• verify/verify-yuki/yuki-0890.test.cpp
• verify/verify-yuki/yuki-0896.test.cpp
• verify/verify-yuki/yuki-1781.test.cpp

Code

#pragma once

// Prime Sieve {2, 3, 5, 7, 11, 13, 17, ...}
vector<int> prime_enumerate(int N) {
  vector<bool> sieve(N / 3 + 1, 1);
  for (int p = 5, d = 4, i = 1, sqn = sqrt(N); p <= sqn; p += d = 6 - d, i++) {
    if (!sieve[i]) continue;
    for (int q = p * p / 3, r = d * p / 3 + (d * p % 3 == 2), s = 2 * p,
             qe = sieve.size();
         q < qe; q += r = s - r)
      sieve[q] = 0;
  }
  vector<int> ret{2, 3};
  for (int p = 5, d = 4, i = 1; p <= N; p += d = 6 - d, i++)
    if (sieve[i]) ret.push_back(p);
  while (!ret.empty() && ret.back() > N) ret.pop_back();
  return ret;
}

#line 2 "prime/prime-enumerate.hpp"

// Prime Sieve {2, 3, 5, 7, 11, 13, 17, ...}
vector<int> prime_enumerate(int N) {
  vector<bool> sieve(N / 3 + 1, 1);
  for (int p = 5, d = 4, i = 1, sqn = sqrt(N); p <= sqn; p += d = 6 - d, i++) {
    if (!sieve[i]) continue;
    for (int q = p * p / 3, r = d * p / 3 + (d * p % 3 == 2), s = 2 * p,
             qe = sieve.size();
         q < qe; q += r = s - r)
      sieve[q] = 0;
  }
  vector<int> ret{2, 3};
  for (int p = 5, d = 4, i = 1; p <= N; p += d = 6 - d, i++)
    if (sieve[i]) ret.push_back(p);
  while (!ret.empty() && ret.back() > N) ret.pop_back();
  return ret;
}

Back to top page