Halc's Library

This documentation is automatically generated by online-judge-tools/verification-helper

---

Project maintained by halc-git Hosted on GitHub Pages — Theme by mattgraham

Math/EnumeratePrimes.hpp

• View this file on GitHub
• Last update: 2024-10-22 17:25:04+09:00
• Include: #include "Math/EnumeratePrimes.hpp"

Required by

• Math/MFPrefixSum.hpp

Verified with

• Verify/verify-yosupo-new/sum_of_multiplicative_function-black_algorithm.test.cpp
• Verify/verify-yosupo-new/sum_of_multiplicative_function-min25_sieve.test.cpp
• Verify/verify-yosupo-number-theory/enumerate_primes.test.cpp
• Verify/verify-yosupo-number-theory/sum_of_totient_function.test.cpp

Code

#pragma once
#include <cstdint>
#include <vector>
std::vector<int32_t> enumerate_primes(int32_t n) {
    std::vector<bool> flg((n + 1) >> 1, true);
    std::vector<int32_t> ret = {2};
    for (int32_t i = 3; i <= n; i += 2) {
        if (!flg[i >> 1]) continue;
        ret.emplace_back(i);
        if (i * i > n) {
            for (int32_t j = i + 2; j <= n; j += 2) {
                if (flg[j >> 1]) ret.emplace_back(j);
            }
            break;
        }
        for (int32_t j = i * i; j <= n; j += i << 1) {
            flg[j >> 1] = false;
        }
    }
    while (!ret.empty() && ret.back() > n) ret.pop_back();
    return ret;
}

#line 2 "Math/EnumeratePrimes.hpp"
#include <cstdint>
#include <vector>
std::vector<int32_t> enumerate_primes(int32_t n) {
    std::vector<bool> flg((n + 1) >> 1, true);
    std::vector<int32_t> ret = {2};
    for (int32_t i = 3; i <= n; i += 2) {
        if (!flg[i >> 1]) continue;
        ret.emplace_back(i);
        if (i * i > n) {
            for (int32_t j = i + 2; j <= n; j += 2) {
                if (flg[j >> 1]) ret.emplace_back(j);
            }
            break;
        }
        for (int32_t j = i * i; j <= n; j += i << 1) {
            flg[j >> 1] = false;
        }
    }
    while (!ret.empty() && ret.back() > n) ret.pop_back();
    return ret;
}

Back to top page