cp-documentation

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

View the Project on GitHub zawa-tin/cp-documentation

:heavy_check_mark: Test/My/Number/EnumeratePrimes.test.cpp

Depends on

Code

#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/courses/lesson/2/ITP1/1/ITP1_1_A"

#include "../../../Src/Number/EratosthenesSieve.hpp"
#include "../../../Src/Number/EnumeratePrimes.hpp"

#include <random>

std::vector<int> EratosEnumerate(int N) {
    std::vector<int> ans;
    for (auto v : zawa::EratosthenesSieve(N).enumeratePrimes(N)) {
        ans.push_back(static_cast<int>(v));
    }
    return ans;
}

bool test(int N) {
    return EratosEnumerate(N) == zawa::EnumeratePrimes<int>(N);
}

#include <cassert>
#include <iostream>
#include <random>

int main() {
    // small
    for (int N = 1 ; N <= 500 ; N++) assert(test(N));
    std::mt19937 mt{std::random_device{}()};
    for (int t = 0 ; t < 15 ; t++) {
        int N = mt() % (int)1e7 + 1;
        assert(test(N));
    }
    std::cout << "Hello World\n";
}
#line 1 "Test/My/Number/EnumeratePrimes.test.cpp"
#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/courses/lesson/2/ITP1/1/ITP1_1_A"

#line 2 "Src/Number/EratosthenesSieve.hpp"

#line 2 "Src/Template/TypeAlias.hpp"

#include <cstdint>
#include <cstddef>

namespace zawa {

using i16 = std::int16_t;
using i32 = std::int32_t;
using i64 = std::int64_t;
using i128 = __int128_t;

using u8 = std::uint8_t;
using u16 = std::uint16_t;
using u32 = std::uint32_t;
using u64 = std::uint64_t;

using usize = std::size_t;

} // namespace zawa
#line 4 "Src/Number/EratosthenesSieve.hpp"

#include <vector>
#include <cassert>
#include <algorithm>

namespace zawa {

class EratosthenesSieve {
private:
    usize tableSize_;
    std::vector<bool> table_;

public:
    EratosthenesSieve() = default;

    EratosthenesSieve(usize tableSize) : tableSize_{ tableSize + 1 }, table_(tableSize + 1, true) {
        table_.shrink_to_fit();
        assert(tableSize_ > 0);
        table_[0] = table_[1] = false;
        for (u64 i = 2 ; i * i < tableSize_ ; i++) {
            if (!table_[i]) continue;
            for (u64 j = i * i ; j < tableSize_ ; j += i ) {
                table_[j] = false;
            }
        }
    }

    inline bool operator[](u32 i) const {
        assert(i < tableSize_);
        return table_[i];
    }

    inline bool isPrime(u32 i) const {
        assert(i < tableSize_);
        return table_[i];
    }

    inline usize size() const {
        return tableSize_ - 1;
    }

    std::vector<u32> enumeratePrimes(u32 N) const {
        assert(N < tableSize_);
        std::vector<u32> primes{};
        primes.reserve(std::count(table_.begin(), table_.begin() + N + 1, true));
        for (u32 i = 2 ; i <= N ; i++) {
            if (table_[i]) {
                primes.emplace_back(i);
            }
        }
        return primes;
    }
};

} // namespace zawa
#line 2 "Src/Number/EnumeratePrimes.hpp"

#line 4 "Src/Number/EnumeratePrimes.hpp"

#include <concepts>
#line 7 "Src/Number/EnumeratePrimes.hpp"
#include <bit>

namespace zawa {

template <std::integral T>
std::vector<T> EnumeratePrimes(usize N) {
    static constexpr u32 p[]{2,3,5,7,11,13,17,19,23,29,31};
    u32 w = 1;
    usize m = 0;
    for ( ; m < std::size(p) and static_cast<u64>(w) * w < N ; w *= p[m++]) ;
    std::vector<u32> R = [&]() {
        std::vector<bool> siv(w, true);
        for (usize i = 0 ; i < m ; i++) {
            for (u32 j = p[i] ; j < w ; j += p[i]) siv[j] = false;
        }
        std::vector<u32> res{1};
        for (u32 i = 2 ; i < w ; i++) if (siv[i]) res.push_back(i);
        return res;
    }();
    std::vector<T> res;
    res.reserve(N / (std::bit_width(N) + 1));
    std::vector<u32> S;
    S.reserve(N / 5u);
    for (u32 kw = 0 ; kw <= N ; kw += w) {
        for (u32 r = 0 ; r < R.size() and kw + R[r] <= N ; r++) {
            S.push_back(kw + R[r]);
        }
    }
    for (usize i = 0 ; i < m ; i++) res.push_back(static_cast<T>(p[i]));
    std::vector<bool> siv(N + 1, true);
    for (usize i = 1 ; i < S.size() ; i++) if (siv[S[i]]) {
        res.push_back(static_cast<T>(S[i])); 
        for (u32 j = i ; j < S.size() ; j++) {
            u64 p = static_cast<u64>(S[i]) * S[j];
            if (p > N) break;
            siv[p] = false;
        }
    }
    return res;
}

} // namespace zawa
#line 5 "Test/My/Number/EnumeratePrimes.test.cpp"

#include <random>

std::vector<int> EratosEnumerate(int N) {
    std::vector<int> ans;
    for (auto v : zawa::EratosthenesSieve(N).enumeratePrimes(N)) {
        ans.push_back(static_cast<int>(v));
    }
    return ans;
}

bool test(int N) {
    return EratosEnumerate(N) == zawa::EnumeratePrimes<int>(N);
}

#line 21 "Test/My/Number/EnumeratePrimes.test.cpp"
#include <iostream>
#line 23 "Test/My/Number/EnumeratePrimes.test.cpp"

int main() {
    // small
    for (int N = 1 ; N <= 500 ; N++) assert(test(N));
    std::mt19937 mt{std::random_device{}()};
    for (int t = 0 ; t < 15 ; t++) {
        int N = mt() % (int)1e7 + 1;
        assert(test(N));
    }
    std::cout << "Hello World\n";
}
Back to top page