提交记录 170244


用户 题目 状态 得分 用时 内存 语言 代码长度
saffah_codex61s_agg5 1022. 测测你的筛法 Accepted 100 1.298 s 1221164 KB C++17 99.57 KB
提交时间 评测时间
2026-11-17 23:22:22 2026-11-17 23:22:39
/* References / 引用: saffah_codex61s_agg5
 https://duck.ac/submission/170236: complete Accepted sieve, marking
 kernels, delayed output and every inherited account/URL/use/notice below.
 saffah_codex61s_agg5 https://duck.ac/submission/170179: explicit GCC64-byte
 hot-loop alignment idea, transferred from the newly verified FKM emitter.
 The complete Kim Walisch BSD-2-Clause notice remains intact.
 Approach / 思路: Apply GCC align-loops=32 to the generated marking and expansion loops while retaining all arithmetic, vector data, segments, stores and
 bounds. Compare complete production object contents/layout/relocations/
 exported symbols with the parent to avoid a source-only equivalent repeat.
 Experiment purpose: if generated code differs, compare all1250000000 sieve
 bytes with independent Accepted reference and64 guards, then immediately
 measure the real official implementation without local performance gating.
 */
/* References / 引用: saffah_v41f1017_agg4 https://duck.ac/submission/168755: complete Accepted sieve, marking kernels, delayed output and every inherited account/URL/use/notice below. saffah_codex61s_agg5 https://duck.ac/submission/170179: explicit GCC64-byte hot-loop alignment idea, transferred from the newly verified FKM emitter. The complete Kim Walisch BSD-2-Clause notice remains intact. */
/* References / 引用: saffah_codex61s_agg5 https://duck.ac/submission/167810: complete Accepted segmented sieve, exact wheel residues7,11,13,17,19,23,29,31, staging stores and bounded tail. Every inherited author, source URL and use remains, with the full Kim Walisch BSD-2-Clause copyright, source conditions and disclaimer retained. */
/* Body -- provenance and local changes, output path only: asm 32-byte load; boundary carry from the previous chunk in a register (exact, no movemask injection); PSHUFB nibble tables replaced by exact and/shift/or formulas (port 5 to ports 0/1); 960-byte tile double-buffered so the previous tile drains non-temporally inside the next generation. Output byte-identical to the cited body, FNV-1a match, prime count 455052511. Original account: saffah_codex61s_agg5; source submission https://duck.ac/submission/167903. The programme below is that adopted text. All inherited citations and the complete Kim Walisch BSD-2-Clause notice below are retained verbatim and apply to this derivative. Change 1: four further constexpr tables extend the periodic pre-sieve to the primes 167..199, so eratSmall no longer marks those eight primes and one extra AND pass replaces them. Change 2: the output staging group is widened from 240 to 960 bytes (fifteen whole 64-byte lines) and drained with thirty 32-byte non-temporal stores. Value-exact vs the cited body. Purpose: measure pre-sieve extension plus wider streamed output at n=1e10. */
/* References / 引用: saffah_codex_6a_agg3 https://duck.ac/submission/163233: complete Accepted128KiB segmented sieve, shifted-PDEP packing and every inherited source/author citation. Preserve the full Kim Walisch primesieve BSD-2-Clause copyright, redistribution conditions and disclaimer below to satisfy its source terms. */
/* References: saffah_v41f1017_agg4 https://duck.ac/submission/163066 complete128KiB sieve; saffah_codex_6a_agg3 https://duck.ac/submission/163024 aligned non-temporal output tiles. All upstream references and Kim Walisch BSD-2-Clause notice retained below. Idea: Preserve128KiB sieving and transfer64 wheel bytes through a240-byte aligned staging tile into streamed output stores, avoiding write allocation on the1.25GB destination. Fence before cached tails and final bits. Experiment: measure output traffic reduction at this scale after full exact verification. */
/* Body -- citation, provenance and the one local change. Original account: saffah_codex_6a_agg3 (https://duck.ac/user/profile/saffah_codex_6a_agg3) Source submission: https://duck.ac/submission/162863 (problem 1022, Accepted, board time 1.38 s) Upstream chain cited by those submissions and retained verbatim below: saffah_codex_6a_agg3 https://duck.ac/submission/162490 (constexpr pre-sieve tables) and https://duck.ac/submission/162799 (shifted pdep mask, direct carry bit), saffah_codex61s_agg5 https://duck.ac/submission/162711 (pdep expansion, constexpr root-prime table, compile-time n), and saffah_codex_maker https://duck.ac/submission/162270 /162354 (primesieve engine, wheel-30 output). What was used: the programme below is that adopted text. One structural change is ours, confined to the bit-expansion lambda: the per-iteration tail test (if(pos+16<=total)) is hoisted out of the hot loop into a counted full-block loop plus a guarded epilogue, so the hot loop contains an unconditional 16-byte store. It is value-exact: the complete output of problem 1022 was compared with the cited body before posting and is byte-identical (same FNV-1a 64-bit hash, same prime count, no write past the end of the output). Licence: the contained engine is Kim Walisch's primesieve, BSD-2-Clause; the complete copyright notice, conditions and disclaimer are retained verbatim below and apply to this derivative as well. Purpose: post the fastest value-correct body this account has for problem 1022. */
/* References: saffah_codex61s_agg5 https://duck.ac/submission/162747:128KiB maximum segment. Complete inherited references and BSD notice follow. */
/* References: saffah_codex61s_agg5 https://duck.ac/submission/162711: constant base-prime list and scale specialization;162744 (same account, https://duck.ac/submission/162744):128KiB cap. All inherited engine references and complete Kim Walisch BSD-2-Clause notice remain below. */
/* References / 引用: saffah_codex_maker https://duck.ac/submission/162354 : copied the complete Accepted wheel30 segmented prime sieve, marking order and packed output. Its submission supplies no separate license. Additional reference: saffah_codex_6a_agg3 https://duck.ac/submission/162672 : copied its complete streamed primesieve and carry-aware table expansion. All inherited Kim Walisch BSD-2-Clause notices and upstream references remain below, satisfying its source redistribution terms. New approach: Compute all base primes up to100000 at compile time by an independently written constexpr Eratosthenes sieve; consume only primes above163 whose squares reach each segment. Remove runtime square-root/small sieve, growing pending vector and its allocations. Specialize the public fixed n, preserving the advanced PDEP carry-aware expansion. Approach / 思路: Compute all base primes up to100000 at compile time by an independently written constexpr Eratosthenes sieve; consume only primes above163 whose squares reach each segment. Remove runtime square-root/small sieve, growing pending vector and its allocations. Specialize the public fixed n, preserving the advanced PDEP carry-aware expansion. Experiment purpose / 试验目的: Compare all 1250000 official-sized output bytes with the cited Accepted implementation and verify64 trailing guard bytes; immediately submit the correct distinct program. No local timing criterion. Fresh Pending 文件个数==0, sharedHTTP2 and exact qualification stop apply. */
/* References: saffah_codex61s_agg5 https://duck.ac/submission/162565: 128-bit overlapping store idea. Base own162490, maker162270 and complete Kim Walisch BSD-2-Clause copyright, terms and disclaimer retained below. */
/* References: saffah_codex_maker https://duck.ac/submission/162270: copy the primesieve engine and base_stream::Generator. Kim Walisch's primesieve https://github.com/kimwalisch/primesieve is BSD-2-Clause; the complete copyright, conditions and disclaimer are retained immediately below. */
// n-only mathematical input.

/* BSD 2-Clause License Copyright (c) 2010 - 2026, Kim Walisch. All rights reserved. Redistribution and use in source and binary forms, with or without modification, are permitted provided that the following conditions are met: 1. Redistributions of source code must retain the above copyright notice, this list of conditions and the following disclaimer. 2. Redistributions in binary form must reproduce the above copyright notice, this list of conditions and the following disclaimer in the documentation and/or other materials provided with the distribution. THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. */
/* Idea: Reuse the compressed30-wheel segmented prime engine for [0,n), and expand four wheel bytes directly into each15-byte output group. Carry the two overlapping high bits into the next group/segment; no separate prime list or full intermediate wheel array is materialized. Purpose: compare all bits with an independent sieve, then measure all currently eligible1022 family sizes officially. Submission requires a fresh /status Pending 文件个数 exactly0. */
/* Idea: Build each periodic pre-sieve table as an independent constexpr object, using 30*j+offset congruences to clear only divisible positions. This removes the startup constructor's repeated trial divisions. Purpose: validate all bits and guards, then measure this distinct implementation officially. */
#include <bits/stdc++.h>
/* Idea: Deposit each16-bit wheel pair into60 output bits with BMI2 PDEP,
then join two pairs into one128-bit store. Replace four lookup loads and their
byte indexing with one32-bit source load and two deposits. Remove the carry
chain within each segment by reading the preceding source byte. Purpose:
full-byte comparison and guards before official measurement. */
/* Idea: The third wheel byte begins at output bit67, so it contributes
nothing to the first output qword. Deposit the second pair directly with a
mask shifted right4; remove the zero low contribution and post-deposit shift.
Carry comes directly from input bit31 in a register. Combine with128KiB
segments to reduce wheel/output working-set pressure. Purpose: full output/guard
comparison then official timing. */
#include <immintrin.h>
#include <x86intrin.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("align-loops=32")
#pragma GCC optimize("align-jumps=32")
#pragma GCC target("avx2,popcnt,bmi2")
#define NDEBUG

#undef CHECK_FINISHED

#ifndef WHEEL_HPP
#define WHEEL_HPP
#ifndef MACROS_HPP
#define MACROS_HPP
#include <utility>
#ifndef __has_attribute
#define __has_attribute(x) 0
#endif
#ifndef __has_builtin
#define __has_builtin(x) 0
#endif
#ifndef __has_cpp_attribute
#define __has_cpp_attribute(x) 0
#endif
#ifndef __has_include
#define __has_include(x) 0
#endif
#if __has_attribute(always_inline)
#define ALWAYS_INLINE inline __attribute__((always_inline))
#elif defined(_MSC_VER)
#define ALWAYS_INLINE inline __forceinline
#else
#define ALWAYS_INLINE inline
#endif
#if __has_attribute(noinline)
#define NOINLINE __attribute__((noinline))
#elif defined(_MSC_VER)
#define NOINLINE __declspec(noinline)
#else
#define NOINLINE
#endif
#if __has_attribute(target)
#define PRIMESIEVE_TARGET_ATTRIBUTE(isa) __attribute__((target(isa)))
#elif defined(_MSC_VER)
#define PRIMESIEVE_TARGET_ATTRIBUTE(isa) NOINLINE
#endif
#if __cplusplus >= 202002L && \
__has_cpp_attribute(likely)
#define if_likely(x) if (x) [[likely]]
#elif defined(__GNUC__) || \
__has_builtin(__builtin_expect)
#define if_likely(x) if (__builtin_expect(!!(x), 1))
#else
#define if_likely(x) if (x)
#endif
#if __cplusplus >= 202002L && \
__has_cpp_attribute(unlikely)
#define if_unlikely(x) if (x) [[unlikely]]
#elif defined(__GNUC__) || \
__has_builtin(__builtin_expect)
#define if_unlikely(x) if (__builtin_expect(!!(x), 0))
#else
#define if_unlikely(x) if (x)
#endif
#if defined(ENABLE_ASSERT)
namespace primesieve {
[[noreturn]]
void assert_failed(const char* assertion,
const char* file,
unsigned int line,
const char* function);
} 
#if defined(_MSC_VER)
#define ASSERT_FUNCTION __FUNCSIG__
#elif defined(__GNUC__) || defined(__clang__)
#define ASSERT_FUNCTION __PRETTY_FUNCTION__
#else
#define ASSERT_FUNCTION __func__
#endif
#define ASSERT(x) \
do { \
if_unlikely(!(x)) \
primesieve::assert_failed(#x, __FILE__, __LINE__, ASSERT_FUNCTION); \
} while (0)
#else
#define ASSERT(x) ((void) 0)
#endif
#if __cplusplus >= 201703L && \
__has_cpp_attribute(fallthrough)
#define FALLTHROUGH [[fallthrough]]
#elif __has_attribute(fallthrough)
#define FALLTHROUGH __attribute__((fallthrough))
#else
#define FALLTHROUGH
#endif
#if defined(__GNUC__) || \
__has_builtin(__builtin_unreachable)
#define UNREACHABLE __builtin_unreachable()
#elif defined(_MSC_VER)
#define UNREACHABLE __assume(0)
#elif __cplusplus >= 202301L && \
defined(__cpp_lib_unreachable)
#define UNREACHABLE std::unreachable()
#else
#define UNREACHABLE
#endif
#if __cplusplus >= 201703L && \
__has_cpp_attribute(maybe_unused)
#define MAYBE_UNUSED [[maybe_unused]]
#elif __has_attribute(unused)
#define MAYBE_UNUSED __attribute__((unused))
#else
#define MAYBE_UNUSED
#endif
#if defined(__GNUC__) && \
!defined(__clang__)
#if __GNUC__ < 12
#undef MAYBE_UNUSED
#define MAYBE_UNUSED
#endif
#endif
#if __has_attribute(uninitialized)
#define INDETERMINATE __attribute__((uninitialized))
#elif __cplusplus >= 202603L && \
__has_cpp_attribute(indeterminate)
#define INDETERMINATE [[indeterminate]]
#else
#define INDETERMINATE
#endif
#if defined(__clang__)
#define NO_UNROLL_LOOP _Pragma("nounroll")
#elif defined(__GNUC__) && __GNUC__ >= 8
#define NO_UNROLL_LOOP _Pragma("GCC unroll 0")
#else
#define NO_UNROLL_LOOP
#endif
#if defined(__clang__)
#define NO_VECTORIZE_LOOP _Pragma("clang loop vectorize(disable)")
#elif defined(__GNUC__) && __GNUC__ >= 14
#define NO_VECTORIZE_LOOP _Pragma("GCC novector")
#elif defined(_MSC_VER)
#define NO_VECTORIZE_LOOP __pragma(loop(no_vector))
#else
#define NO_VECTORIZE_LOOP
#endif
#endif
#include <stdint.h>
#include <algorithm>
namespace primesieve {
struct WheelInit
{
uint8_t nextMultipleFactor;
uint8_t wheelIndex;
};
extern const WheelInit wheel30Init[30];
extern const WheelInit wheel210Init[210];
template <int MODULO,
int SIZE,
int MAXMULTIPLEFACTOR,
const WheelInit* INIT>
class Wheel
{
public:
void addSievingPrime(uint64_t prime, uint64_t segmentLow)
{
ASSERT(segmentLow % 30 == 0);
segmentLow += 6;
uint64_t quotient = (segmentLow / prime) + 1;
quotient = std::max(prime, quotient);
uint64_t multiple = prime * quotient;
if (multiple > stop_ ||
multiple < segmentLow)
return;
uint64_t nextMultipleFactor = INIT[quotient % MODULO].nextMultipleFactor;
uint64_t nextMultiple = prime * nextMultipleFactor;
if (nextMultiple > stop_ - multiple)
return;
multiple += nextMultiple;
#if defined(ENABLE_ASSERT)
if (MODULO >=    2) ASSERT(multiple %  2 != 0);
if (MODULO >=    6) ASSERT(multiple %  3 != 0);
if (MODULO >=   30) ASSERT(multiple %  5 != 0);
if (MODULO >=  210) ASSERT(multiple %  7 != 0);
if (MODULO >= 2310) ASSERT(multiple % 11 != 0);
#endif
uint64_t multipleIndex = (multiple - segmentLow) / 30;
uint64_t wheelIndex = wheelOffsets_[prime % 30] + INIT[quotient % MODULO].wheelIndex;
storeSievingPrime(prime, multipleIndex, wheelIndex);
}
protected:
uint64_t stop_ = 0;
virtual ~Wheel() = default;
virtual void storeSievingPrime(uint64_t, uint64_t, uint64_t) = 0;
static uint64_t getMaxFactor()
{
return MAXMULTIPLEFACTOR;
}
private:
static const uint64_t wheelOffsets_[30];
};
template <int MODULO,
int SIZE,
int MAXMULTIPLEFACTOR,
const WheelInit* INIT>
const uint64_t
Wheel<MODULO, SIZE, MAXMULTIPLEFACTOR, INIT>::wheelOffsets_[30] =
{
0, SIZE * 7, 0, 0, 0, 0,
0, SIZE * 0, 0, 0, 0, SIZE * 1,
0, SIZE * 2, 0, 0, 0, SIZE * 3,
0, SIZE * 4, 0, 0, 0, SIZE * 5,
0, 0,        0, 0, 0, SIZE * 6
};
using Wheel30_t = Wheel<30, 8, 6, wheel30Init>;
using Wheel210_t = Wheel<210, 48, 10, wheel210Init>;
} 
#endif
#ifndef FORWARD_HPP
#define FORWARD_HPP
#ifndef VECTOR_HPP
#define VECTOR_HPP
#include <algorithm>
#include <cstddef>
#include <memory>
#include <stdint.h>
#include <type_traits>
#include <stdexcept>
#include <utility>
namespace primesieve {
template <typename T, typename Allocator>
struct VectorBase
{
T* begin_ = nullptr;
T* end_ = nullptr;
T* capacity_ = nullptr;
VectorBase() noexcept = default;
~VectorBase() noexcept
{
if (begin_)
{
ASSERT(capacity_ >= begin_);
std::size_t cap = std::size_t(capacity_ - begin_);
Allocator().deallocate(begin_, cap);
}
}
VectorBase(VectorBase&& other) noexcept
: begin_(other.begin_),
end_(other.end_),
capacity_(other.capacity_)
{
other.begin_ = nullptr;
other.end_ = nullptr;
other.capacity_ = nullptr;
}
VectorBase(const VectorBase&) = delete;
VectorBase& operator=(const VectorBase&) = delete;
};
template <typename T,
typename Allocator = std::allocator<T>>
class Vector : private VectorBase<T, Allocator>
{
using VecBase = VectorBase<T, Allocator>;
using VecBase::begin_;
using VecBase::end_;
using VecBase::capacity_;
public:
static_assert(std::allocator_traits<Allocator>::is_always_equal::value,
"Vector<T> only supports stateless allocators!");
using value_type = T;
Vector() noexcept = default;
Vector(std::size_t size)
{
resize(size);
}
~Vector() noexcept
{
destroy(begin_, end_);
}
void deallocate() noexcept
{
if (begin_)
{
destroy(begin_, end_);
Allocator().deallocate(begin_, capacity());
begin_ = nullptr;
end_ = nullptr;
capacity_ = nullptr;
}
}
void clear() noexcept
{
destroy(begin_, end_);
end_ = begin_;
}
Vector(const Vector&) = delete;
Vector& operator=(const Vector&) = delete;
Vector(Vector&& other) noexcept
: VecBase(std::move(other))
{ }
Vector& operator=(Vector&& other) noexcept
{
if (this != &other)
{
deallocate();
begin_ = other.begin_;
end_ = other.end_;
capacity_ = other.capacity_;
other.begin_ = nullptr;
other.end_ = nullptr;
other.capacity_ = nullptr;
}
return *this;
}
void swap(Vector& other) noexcept
{
T* tmp_array = begin_;
T* tmp_end = end_;
T* tmp_capacity = capacity_;
begin_ = other.begin_;
end_ = other.end_;
capacity_ = other.capacity_;
other.begin_ = tmp_array;
other.end_ = tmp_end;
other.capacity_ = tmp_capacity;
}
bool empty() const noexcept
{
return begin_ == end_;
}
T& operator[](std::size_t pos) noexcept
{
ASSERT(pos < size());
return begin_[pos];
}
const T& operator[](std::size_t pos) const noexcept
{
ASSERT(pos < size());
return begin_[pos];
}
T& at(std::size_t pos)
{
if_unlikely(pos >= size())
throw std::out_of_range("Vector: pos >= size() detected!");
return begin_[pos];
}
const T& at(std::size_t pos) const
{
if_unlikely(pos >= size())
throw std::out_of_range("Vector: pos >= size() detected!");
return begin_[pos];
}
T* data() noexcept
{
return begin_;
}
const T* data() const noexcept
{
return begin_;
}
std::size_t size() const noexcept
{
ASSERT(end_ >= begin_);
return std::size_t(end_ - begin_);
}
std::size_t capacity() const noexcept
{
ASSERT(capacity_ >= begin_);
return std::size_t(capacity_ - begin_);
}
T* begin() noexcept
{
return begin_;
}
const T* begin() const noexcept
{
return begin_;
}
T* end() noexcept
{
return end_;
}
const T* end() const noexcept
{
return end_;
}
T& front() noexcept
{
ASSERT(!empty());
return *begin_;
}
const T& front() const noexcept
{
ASSERT(!empty());
return *begin_;
}
T& back() noexcept
{
ASSERT(!empty());
return *(end_ - 1);
}
const T& back() const noexcept
{
ASSERT(!empty());
return *(end_ - 1);
}
ALWAYS_INLINE void push_back(const T& value)
{
if_likely(end_ != capacity_)
{
new(end_) T(value);
end_++;
}
else
emplace_back_reallocate(value);
}
ALWAYS_INLINE void push_back(T&& value)
{
if_likely(end_ != capacity_)
{
new(end_) T(std::move(value));
end_++;
}
else
emplace_back_reallocate(std::move(value));
}
template <class... Args>
ALWAYS_INLINE void emplace_back(Args&&... args)
{
if_likely(end_ != capacity_)
{
new(end_) T(std::forward<Args>(args)...);
end_++;
}
else
emplace_back_reallocate(std::forward<Args>(args)...);
}
template <class InputIt>
void insert(T* const pos, InputIt first, InputIt last)
{
ASSERT(pos == end_);
(void) pos;
if_likely(first < last)
{
std::size_t count = std::size_t(last - first);
if (size() + count <= capacity())
{
std::uninitialized_copy(first, last, end_);
end_ += count;
}
else
insert_reallocate(first, last);
}
}
void reserve(std::size_t n)
{
if (n > capacity())
reserve_unchecked(n);
}
void resize(std::size_t n)
{
if (n > size())
{
if (n > capacity())
reserve_unchecked(n);
uninitialized_default_construct(end_, begin_ + n);
end_ = begin_ + n;
}
else if (n < size())
{
destroy(begin_ + n, end_);
end_ = begin_ + n;
}
}
private:
std::size_t increase_capacity() const
{
std::size_t new_capacity = capacity() * 2;
std::size_t min_capacity = std::max(std::size_t(1), 16 / sizeof(T));
new_capacity = std::max(min_capacity, new_capacity);
ASSERT(capacity() < new_capacity);
return new_capacity;
}
void reserve_unchecked(std::size_t n)
{
ASSERT(n > capacity());
ASSERT(size() <= capacity());
std::size_t old_size = size();
std::size_t old_capacity = capacity();
std::size_t new_capacity = increase_capacity();
new_capacity = std::max(new_capacity, n);
ASSERT(capacity() < new_capacity);
T* old = begin_;
begin_ = Allocator().allocate(new_capacity);
end_ = begin_ + old_size;
capacity_ = begin_ + new_capacity;
ASSERT(size() < capacity());
if (old)
{
static_assert(std::is_nothrow_move_constructible<T>::value,
"Vector<T> only supports nothrow moveable types!");
uninitialized_move_n(old, old_size, begin_);
destroy(old, old + old_size);
Allocator().deallocate(old, old_capacity);
}
}
template <class... Args>
void emplace_back_reallocate(Args&&... args)
{
std::size_t old_size = size();
std::size_t old_capacity = capacity();
std::size_t new_capacity = increase_capacity();
ASSERT(capacity() < new_capacity);
struct AllocateMemory
{
T* begin = nullptr;
std::size_t capacity = 0;
AllocateMemory(std::size_t cap)
{
begin = Allocator().allocate(cap);
capacity = cap;
}
~AllocateMemory()
{
if (begin)
Allocator().deallocate(begin, capacity);
}
};
AllocateMemory new_mem(new_capacity);
new (new_mem.begin + old_size) T(std::forward<Args>(args)...);
if (begin_)
{
static_assert(std::is_nothrow_move_constructible<T>::value,
"Vector<T> only supports nothrow moveable types!");
uninitialized_move_n(begin_, old_size, new_mem.begin);
destroy(begin_, end_);
Allocator().deallocate(begin_, old_capacity);
}
begin_ = new_mem.begin;
end_ = begin_ + old_size + 1;
capacity_ = begin_ + new_capacity;
new_mem.begin = nullptr;
}
template <class InputIt>
void insert_reallocate(InputIt first, InputIt last)
{
ASSERT(first < last);
std::size_t old_size = size();
std::size_t count = std::size_t(last - first);
std::size_t new_size = old_size + count;
std::size_t old_capacity = capacity();
std::size_t new_capacity = increase_capacity();
new_capacity = std::max(new_capacity, new_size);
ASSERT(capacity() < new_capacity);
struct AllocateMemory
{
T* begin = nullptr;
std::size_t capacity = 0;
AllocateMemory(std::size_t cap)
{
begin = Allocator().allocate(cap);
capacity = cap;
}
~AllocateMemory()
{
if (begin)
Allocator().deallocate(begin, capacity);
}
};
AllocateMemory new_mem(new_capacity);
std::uninitialized_copy(first, last, new_mem.begin + old_size);
if (begin_)
{
static_assert(std::is_nothrow_move_constructible<T>::value,
"Vector<T> only supports nothrow moveable types!");
uninitialized_move_n(begin_, old_size, new_mem.begin);
destroy(begin_, end_);
Allocator().deallocate(begin_, old_capacity);
}
begin_ = new_mem.begin;
end_ = begin_ + new_size;
capacity_ = begin_ + new_capacity;
new_mem.begin = nullptr;
}
template <typename TT = T>
ALWAYS_INLINE typename std::enable_if<std::is_trivially_default_constructible<TT>::value, void>::type
uninitialized_default_construct(T* first, T* last)
{
for (; first != last; first++)
new (first) T;
}
template <typename TT = T>
ALWAYS_INLINE typename std::enable_if<!std::is_trivially_default_constructible<TT>::value, void>::type
uninitialized_default_construct(T* first, T* last)
{
struct ExceptionGuard
{
Vector* vec_;
T* pos_;
T* first_;
T* last_;
ExceptionGuard(Vector* vector, T* first, T* last)
: vec_(vector),
pos_(first),
first_(first),
last_(last)
{ }
~ExceptionGuard()
{
if (pos_ != last_)
vec_->destroy(first_, pos_);
}
};
ExceptionGuard guard(this, first, last);
for (; guard.pos_ != guard.last_; guard.pos_++)
new (guard.pos_) T;
}
template <typename TT = T>
ALWAYS_INLINE typename std::enable_if<std::is_trivially_copyable<TT>::value, void>::type
uninitialized_move_n(T* __restrict first,
std::size_t count,
T* __restrict d_first)
{
std::uninitialized_copy_n(first, count, d_first);
}
template <typename TT = T>
ALWAYS_INLINE typename std::enable_if<!std::is_trivially_copyable<TT>::value, void>::type
uninitialized_move_n(T* __restrict first,
std::size_t count,
T* __restrict d_first)
{
for (std::size_t i = 0; i < count; i++)
new (d_first++) T(std::move(*first++));
}
template <typename TT = T>
ALWAYS_INLINE typename std::enable_if<std::is_trivially_destructible<TT>::value, void>::type
destroy(T*, T*)
{ }
template <typename TT = T>
ALWAYS_INLINE typename std::enable_if<!std::is_trivially_destructible<TT>::value, void>::type
destroy(T* first, T* last)
{
while (first != last)
(--last)->~T();
}
};
template <typename T, std::size_t N>
class Array
{
public:
using value_type = T;
T array_[N];
constexpr T& operator[](std::size_t pos) noexcept
{
ASSERT(pos < size());
return array_[pos];
}
constexpr const T& operator[](std::size_t pos) const noexcept
{
ASSERT(pos < size());
return array_[pos];
}
void fill(const T& value)
{
std::fill_n(begin(), size(), value);
}
constexpr T* data() noexcept
{
return array_;
}
constexpr const T* data() const noexcept
{
return array_;
}
constexpr T* begin() noexcept
{
return array_;
}
constexpr const T* begin() const noexcept
{
return array_;
}
constexpr T* end() noexcept
{
return array_ + N;
}
constexpr const T* end() const noexcept
{
return array_ + N;
}
constexpr T& back() noexcept
{
ASSERT(N > 0);
return array_[N - 1];
}
constexpr const T& back() const noexcept
{
ASSERT(N > 0);
return array_[N - 1];
}
constexpr std::size_t size() const noexcept
{
return N;
}
};
} 
#endif
#include <stdint.h>
namespace primesieve {
extern const Array<uint64_t, 65> bitValues;
extern const Array<uint64_t, 64> bruijnBitValues;
int get_num_threads();
int get_sieve_size();
uint64_t get_max_stop();
uint64_t popcount(const Vector<uint64_t>& vect);
} 
#endif
#include <stdint.h>
namespace primesieve {
const Array<uint64_t, 65> bitValues =
{
7,  11,  13,  17,  19,  23,  29, 31,
37,  41,  43,  47,  49,  53,  59, 61,
67,  71,  73,  77,  79,  83,  89, 91,
97, 101, 103, 107, 109, 113, 119, 121,
127, 131, 133, 137, 139, 143, 149, 151,
157, 161, 163, 167, 169, 173, 179, 181,
187, 191, 193, 197, 199, 203, 209, 211,
217, 221, 223, 227, 229, 233, 239, 241,
0
};
const Array<uint64_t, 64> bruijnBitValues =
{
7,  47,  11,  49,  67, 113,  13,  53,
89,  71, 161, 101, 119, 187,  17, 233,
59,  79,  91,  73, 133, 139, 163, 103,
149, 121, 203, 169, 191, 217,  19, 239,
43,  61, 109,  83, 157,  97, 181, 229,
77, 131, 137, 143, 199, 167, 211,  41,
107, 151, 179, 227, 127, 197, 209,  37,
173, 223, 193,  31, 221,  29,  23, 241
};
const WheelInit wheel30Init[30] =
{
{ 1, 0 }, { 0, 0 }, { 5, 1 }, { 4, 1 }, { 3, 1}, { 2, 1 }, { 1, 1 }, { 0, 1 },
{ 3, 2 }, { 2, 2 }, { 1, 2 }, { 0, 2 }, { 1, 3}, { 0, 3 }, { 3, 4 }, { 2, 4 },
{ 1, 4 }, { 0, 4 }, { 1, 5 }, { 0, 5 }, { 3, 6}, { 2, 6 }, { 1, 6 }, { 0, 6 },
{ 5, 7 }, { 4, 7 }, { 3, 7 }, { 2, 7 }, { 1, 7}, { 0, 7 }
};
const WheelInit wheel210Init[210] =
{
{ 1, 0 },  { 0, 0 },  { 9, 1 },  { 8, 1 },  { 7, 1 },  { 6, 1 },  { 5, 1 },  { 4, 1 },
{ 3, 1 },  { 2, 1 },  { 1, 1 },  { 0, 1 },  { 1, 2 },  { 0, 2 },  { 3, 3 },  { 2, 3 },
{ 1, 3 },  { 0, 3 },  { 1, 4 },  { 0, 4 },  { 3, 5 },  { 2, 5 },  { 1, 5 },  { 0, 5 },
{ 5, 6 },  { 4, 6 },  { 3, 6 },  { 2, 6 },  { 1, 6 },  { 0, 6 },  { 1, 7 },  { 0, 7 },
{ 5, 8 },  { 4, 8 },  { 3, 8 },  { 2, 8 },  { 1, 8 },  { 0, 8 },  { 3, 9 },  { 2, 9 },
{ 1, 9 },  { 0, 9 },  { 1, 10 }, { 0, 10 }, { 3, 11 }, { 2, 11 }, { 1, 11 }, { 0, 11 },
{ 5, 12 }, { 4, 12 }, { 3, 12 }, { 2, 12 }, { 1, 12 }, { 0, 12 }, { 5, 13 }, { 4, 13 },
{ 3, 13 }, { 2, 13 }, { 1, 13 }, { 0, 13 }, { 1, 14 }, { 0, 14 }, { 5, 15 }, { 4, 15 },
{ 3, 15 }, { 2, 15 }, { 1, 15 }, { 0, 15 }, { 3, 16 }, { 2, 16 }, { 1, 16 }, { 0, 16 },
{ 1, 17 }, { 0, 17 }, { 5, 18 }, { 4, 18 }, { 3, 18 }, { 2, 18 }, { 1, 18 }, { 0, 18 },
{ 3, 19 }, { 2, 19 }, { 1, 19 }, { 0, 19 }, { 5, 20 }, { 4, 20 }, { 3, 20 }, { 2, 20 },
{ 1, 20 }, { 0, 20 }, { 7, 21 }, { 6, 21 }, { 5, 21 }, { 4, 21 }, { 3, 21 }, { 2, 21 },
{ 1, 21 }, { 0, 21 }, { 3, 22 }, { 2, 22 }, { 1, 22 }, { 0, 22 }, { 1, 23 }, { 0, 23 },
{ 3, 24 }, { 2, 24 }, { 1, 24 }, { 0, 24 }, { 1, 25 }, { 0, 25 }, { 3, 26 }, { 2, 26 },
{ 1, 26 }, { 0, 26 }, { 7, 27 }, { 6, 27 }, { 5, 27 }, { 4, 27 }, { 3, 27 }, { 2, 27 },
{ 1, 27 }, { 0, 27 }, { 5, 28 }, { 4, 28 }, { 3, 28 }, { 2, 28 }, { 1, 28 }, { 0, 28 },
{ 3, 29 }, { 2, 29 }, { 1, 29 }, { 0, 29 }, { 5, 30 }, { 4, 30 }, { 3, 30 }, { 2, 30 },
{ 1, 30 }, { 0, 30 }, { 1, 31 }, { 0, 31 }, { 3, 32 }, { 2, 32 }, { 1, 32 }, { 0, 32 },
{ 5, 33 }, { 4, 33 }, { 3, 33 }, { 2, 33 }, { 1, 33 }, { 0, 33 }, { 1, 34 }, { 0, 34 },
{ 5, 35 }, { 4, 35 }, { 3, 35 }, { 2, 35 }, { 1, 35 }, { 0, 35 }, { 5, 36 }, { 4, 36 },
{ 3, 36 }, { 2, 36 }, { 1, 36 }, { 0, 36 }, { 3, 37 }, { 2, 37 }, { 1, 37 }, { 0, 37 },
{ 1, 38 }, { 0, 38 }, { 3, 39 }, { 2, 39 }, { 1, 39 }, { 0, 39 }, { 5, 40 }, { 4, 40 },
{ 3, 40 }, { 2, 40 }, { 1, 40 }, { 0, 40 }, { 1, 41 }, { 0, 41 }, { 5, 42 }, { 4, 42 },
{ 3, 42 }, { 2, 42 }, { 1, 42 }, { 0, 42 }, { 3, 43 }, { 2, 43 }, { 1, 43 }, { 0, 43 },
{ 1, 44 }, { 0, 44 }, { 3, 45 }, { 2, 45 }, { 1, 45 }, { 0, 45 }, { 1, 46 }, { 0, 46 },
{ 9, 47 }, { 8, 47 }, { 7, 47 }, { 6, 47 }, { 5, 47 }, { 4, 47 }, { 3, 47 }, { 2, 47 },
{ 1, 47 }, { 0, 47 }
};
} 

#undef CHECK_FINISHED

#ifndef MEMORYPOOL_HPP
#define MEMORYPOOL_HPP
namespace primesieve {
class SievingPrime;
class Bucket;
class MemoryPool
{
public:
// Call only after every client holding Bucket pointers has been destroyed.
// Retain and recycle all owned chunks across disjoint prime bands.
void resetReuse();
std::size_t ownedBytes() const;
NOINLINE void addBucket(SievingPrime*& sievingPrime);
void freeBucket(Bucket* bucket);
private:
void updateAllocCount();
void allocateBuckets();
void initBuckets(void* alignedPtr);
Bucket* stock_ = nullptr;
std::size_t count_ = 0;
Vector<Vector<char>> memory_;
};
} 
#endif
#ifndef BUCKET_HPP
#define BUCKET_HPP
#ifndef CONFIG_HPP
#define CONFIG_HPP
#include <stdint.h>
namespace {
namespace config {
constexpr uint64_t L1D_CACHE_BYTES = 32 << 10;
constexpr uint64_t BUCKET_BYTES = 8 << 10;
constexpr uint64_t MAX_ALLOC_BYTES = 16 << 20;
constexpr uint64_t MIN_CACHE_ITERATOR = 4 << 20;
constexpr uint64_t MAX_CACHE_ITERATOR = 1 << 30;
constexpr uint64_t MIN_THREAD_DISTANCE = (uint64_t) 1e7;
constexpr int MAX_CACHE_LINE_SIZE = 512;
constexpr double FACTOR_SIEVESIZE = 2.0;
constexpr double FACTOR_ERATSMALL = 0.15;
constexpr double FACTOR_ERATMEDIUM = 3.0;
} 
} 
#endif
#ifndef PMATH_HPP
#define PMATH_HPP
#include <stdint.h>
#include <algorithm>
#include <cmath>
#include <cstddef>
#include <limits>
#include <type_traits>
#if __cplusplus >= 202002L
#include <bit>
#endif
#if !defined(__has_builtin)
#define __has_builtin(x) 0
#endif
namespace primesieve {
template <typename X, typename Y>
X ceilDiv(X x, Y y)
{
return (X) ((x + y - 1) / y);
}
template <typename A, typename B, typename C>
B inBetween(A min, B x, C max)
{
using T = typename std::common_type<A, B, C>::type;
if ((T) x < (T) min)
return (B) min;
if ((T) x > (T) max)
return (B) max;
return x;
}
template <typename T>
constexpr bool isPow2(T x)
{
return x != 0 && (x & (x - 1)) == 0;
}
template <typename T>
constexpr T numberOfBits()
{
return (T) std::numeric_limits<
typename std::make_unsigned<T>::type
>::digits;
}
template <typename T>
T floorPow2(T x)
{
#if __cplusplus >= 202002L
if (x == 0)
return 0;
auto ux = std::make_unsigned_t<T>(x);
return ((T) 1) << (std::bit_width(ux) - 1);
#elif __has_builtin(__builtin_clzll)
if (x == 0)
return 0;
static_assert(sizeof(T) <= sizeof(unsigned long long), "Unsupported type, wider than long long!");
auto bits = numberOfBits<unsigned long long>();
T ilog2_x = (T) ((bits - 1) - __builtin_clzll(x));
return ((T) 1) << ilog2_x;
#else
for (T i = 1; i < numberOfBits<T>(); i += i)
x |= (x >> i);
return x - (x >> 1);
#endif
}
template <typename T>
T ilog2(T x)
{
#if __cplusplus >= 202002L
auto ux = std::make_unsigned_t<T>(x);
ux = (ux > 0) ? ux : 1;
return std::bit_width(ux) - 1;
#elif __has_builtin(__builtin_clzll)
static_assert(sizeof(T) <= sizeof(unsigned long long), "Unsupported type, wider than long long!");
auto bits = numberOfBits<unsigned long long>();
x = (x > 0) ? x : 1;
return (T) ((bits - 1) - __builtin_clzll(x));
#else
T log2 = 0;
T bits = numberOfBits<T>();
for (T i = bits / 2; i > 0; i /= 2)
{
T one = 1;
if (x >= (one << i))
{
x >>= i;
log2 += i;
}
}
return log2;
#endif
}
template <typename T>
T maxPrimeGap(T n)
{
double x = (double) n;
x = std::max(8.0, x);
double logx = std::log(x);
double prime_gap = logx * logx;
return (T) prime_gap;
}
#if __cplusplus >= 202002L
template <typename T>
consteval T ctSqrt(T x, T lo, T hi)
{
if (lo == hi)
return lo;
const T mid = (lo + hi + 1) / 2;
if (x / mid < mid)
return ctSqrt<T>(x, lo, mid - 1);
else
return ctSqrt(x, mid, hi);
}
template <typename T>
consteval T ctSqrt(T x)
{
return ctSqrt<T>(x, 0, x / 2 + 1);
}
#elif __cplusplus >= 201402L
template <typename T>
constexpr T ctSqrt(T x, T lo, T hi)
{
if (lo == hi)
return lo;
const T mid = (lo + hi + 1) / 2;
if (x / mid < mid)
return ctSqrt<T>(x, lo, mid - 1);
else
return ctSqrt(x, mid, hi);
}
template <typename T>
constexpr T ctSqrt(T x)
{
return ctSqrt<T>(x, 0, x / 2 + 1);
}
#else
#define MID ((lo + hi + 1) / 2)
template <typename T>
constexpr T ctSqrt(T x, T lo, T hi)
{
return lo == hi ? lo : ((x / MID < MID)
? ctSqrt<T>(x, lo, MID - 1) : ctSqrt<T>(x, MID, hi));
}
template <typename T>
constexpr T ctSqrt(T x)
{
return ctSqrt<T>(x, 0, x / 2 + 1);
}
#endif
template <typename T>
T isqrt(T x)
{
T s = (T) std::sqrt((double) x);
constexpr T sqrt_max = ctSqrt(std::numeric_limits<T>::max());
T r = std::min(s, sqrt_max);
if (r * r > x)
{
do { r--; }
while (r * r > x);
}
else if (r * 2 < x - r * r)
{
do { r++; }
while (r * 2 < x - r * r);
}
return r;
}
inline uint64_t checkedAdd(uint64_t x, uint64_t y)
{
if (x >= std::numeric_limits<uint64_t>::max() - y)
return std::numeric_limits<uint64_t>::max();
else
return x + y;
}
inline uint64_t checkedSub(uint64_t x, uint64_t y)
{
if (x > y)
return x - y;
else
return 0;
}
inline std::size_t primeCountUpper(uint64_t start, uint64_t stop)
{
if (start > stop)
return 0;
double x = std::max(100.0, (double) stop);
double pix = (stop - start) / (std::log(x) - 1.1) + 5;
if (pix > (double) std::numeric_limits<std::size_t>::max())
return std::numeric_limits<std::size_t>::max();
return (std::size_t) pix;
}
inline std::size_t primeCountUpper(uint64_t stop)
{
return primeCountUpper(0, stop);
}
} 
#endif
#include <stdint.h>
#include <cstddef>
namespace primesieve {
class SievingPrime
{
public:
enum {
MAX_MULTIPLEINDEX = (1 << 23) - 1,
MAX_WHEELINDEX    = (1 << (32 - 23)) - 1
};
SievingPrime() = default;
SievingPrime(std::size_t sievingPrime,
std::size_t multipleIndex,
std::size_t wheelIndex)
{
set(sievingPrime, multipleIndex, wheelIndex);
}
void set(std::size_t multipleIndex,
std::size_t wheelIndex)
{
ASSERT(multipleIndex <= MAX_MULTIPLEINDEX);
ASSERT(wheelIndex <= MAX_WHEELINDEX);
indexes_ = (uint32_t) (multipleIndex | (wheelIndex << 23));
}
void set(std::size_t sievingPrime,
std::size_t multipleIndex,
std::size_t wheelIndex)
{
ASSERT(multipleIndex <= MAX_MULTIPLEINDEX);
ASSERT(wheelIndex <= MAX_WHEELINDEX);
indexes_ = (uint32_t) (multipleIndex | (wheelIndex << 23));
sievingPrime_ = (uint32_t) sievingPrime;
}
std::size_t getSievingPrime() const
{
return sievingPrime_;
}
std::size_t getMultipleIndex() const
{
return indexes_ & MAX_MULTIPLEINDEX;
}
std::size_t getWheelIndex() const
{
return indexes_ >> 23;
}
private:
uint32_t indexes_;
uint32_t sievingPrime_;
};
class Bucket
{
public:
SievingPrime* begin() { return &sievingPrimes_[0]; }
SievingPrime* end()   { return end_; }
Bucket* next()        { return next_; }
void setNext(Bucket* next) { next_ = next; }
void setEnd(SievingPrime* end) { end_ = end; }
void reset() { end_ = begin(); }
bool empty() { return begin() == end(); }
static Bucket* get(SievingPrime* sievingPrime)
{
ASSERT(sievingPrime != nullptr);
uintptr_t address = (uintptr_t) (void*) sievingPrime;
address -= 1;
address -= address % sizeof(Bucket);
return (Bucket*) (void*) address;
}
static bool isFull(SievingPrime* sievingPrime)
{
uintptr_t address = (uintptr_t) (void*) sievingPrime;
return address % sizeof(Bucket) == 0;
}
private:
enum {
SIEVING_PRIMES_OFFSET = sizeof(SievingPrime*) + sizeof(Bucket*),
SIEVING_PRIMES_SIZE = (config::BUCKET_BYTES - SIEVING_PRIMES_OFFSET) / sizeof(SievingPrime)
};
SievingPrime* end_;
Bucket* next_;
SievingPrime sievingPrimes_[SIEVING_PRIMES_SIZE];
};
static_assert(isPow2(sizeof(Bucket)), "sizeof(Bucket) must be a power of 2!");
} 
#endif
#ifndef PRIMESIEVE_ERROR_HPP
#define PRIMESIEVE_ERROR_HPP
#include <stdexcept>
#include <string>
namespace primesieve {
class primesieve_error : public std::runtime_error
{
public:
primesieve_error(const std::string& msg)
: std::runtime_error(msg)
{ }
};
} 
#endif
#include <stdint.h>
#include <algorithm>
#include <memory>
namespace primesieve {
void MemoryPool::resetReuse()
{
stock_ = nullptr;
for (auto& memory : memory_)
{
std::size_t bytes = memory.size();
void* ptr = memory.data();
if (!std::align(sizeof(Bucket), sizeof(Bucket), ptr, bytes))
throw primesieve_error("MemoryPool: invalid owned chunk during reset!");
auto* buckets = static_cast<Bucket*>(ptr);
const std::size_t count = bytes / sizeof(Bucket);
for (std::size_t i = 0; i < count; ++i)
{
buckets[i].reset();
buckets[i].setNext(stock_);
stock_ = &buckets[i];
}
}
}
std::size_t MemoryPool::ownedBytes() const
{
std::size_t bytes = 0;
for (const auto& memory : memory_) bytes += memory.capacity();
return bytes;
}
void MemoryPool::updateAllocCount()
{
std::size_t allocationNr = memory_.size() + 1;
if (allocationNr == 1)
{
count_ = 73;
memory_.reserve(64);
}
else if (allocationNr == 2)
{
std::size_t minBuckets = 16;
count_ = std::max(minBuckets, count_ / 4);
}
else
{
count_ += count_ / 8;
std::size_t maxCount = config::MAX_ALLOC_BYTES / sizeof(Bucket);
count_ = std::min(count_, maxCount);
}
}
void MemoryPool::allocateBuckets()
{
updateAllocCount();
std::size_t bytes = count_ * sizeof(Bucket);
memory_.emplace_back(bytes);
void* ptr = (void*) memory_.back().data();
if_unlikely(!std::align(sizeof(Bucket), sizeof(Bucket), ptr, bytes))
throw primesieve_error("MemoryPool: failed to align memory!");
count_ = bytes / sizeof(Bucket);
initBuckets(ptr);
}
void MemoryPool::initBuckets(void* alignedPtr)
{
Bucket* buckets = (Bucket*) alignedPtr;
if_unlikely(uintptr_t(buckets) % sizeof(Bucket) != 0)
throw primesieve_error("MemoryPool: failed to align memory!");
if_unlikely(count_ < 10)
throw primesieve_error("MemoryPool: insufficient buckets allocated!");
for (std::size_t i = 0; i < count_; i++)
new (&buckets[i]) Bucket;
for (std::size_t i = 0; i < count_ - 1; i++)
{
buckets[i].reset();
buckets[i].setNext(&buckets[i + 1]);
}
buckets[count_ - 1].reset();
buckets[count_ - 1].setNext(nullptr);
stock_ = buckets;
}
void MemoryPool::addBucket(SievingPrime*& sievingPrime)
{
if (!stock_)
allocateBuckets();
Bucket* bucket = stock_;
stock_ = stock_->next();
bucket->setNext(nullptr);
if (sievingPrime)
{
Bucket* old = Bucket::get(sievingPrime);
old->setEnd(sievingPrime);
bucket->setNext(old);
}
sievingPrime = bucket->begin();
}
void MemoryPool::freeBucket(Bucket* bucket)
{
bucket->reset();
bucket->setNext(stock_);
stock_ = bucket;
}
} 

#undef CHECK_FINISHED

#ifndef ERATSMALL_HPP
#define ERATSMALL_HPP
#include <cstddef>
#include <stdint.h>
namespace primesieve {
class EratSmall : public Wheel30_t
{
public:
void init(uint64_t, uint64_t, uint64_t);
void crossOff(Vector<uint64_t>& sieve);
bool hasSievingPrimes() const { return !primes_.empty(); }
public: // adaptation: expose relative-state insertion
uint64_t maxPrime_ = 0;
std::size_t l1CacheSize_ = 0;
Vector<SievingPrime> primes_;
void storeSievingPrime(uint64_t, uint64_t, uint64_t);
NOINLINE void crossOff(uint8_t*, std::size_t);
};
} 
#endif
#ifndef BITS_HPP
#define BITS_HPP
enum
{
BIT0 = 0xfe, 
BIT1 = 0xfd, 
BIT2 = 0xfb, 
BIT3 = 0xf7, 
BIT4 = 0xef, 
BIT5 = 0xdf, 
BIT6 = 0xbf, 
BIT7 = 0x7f  
};
#endif
#include <stdint.h>
#include <algorithm>
namespace primesieve {
void EratSmall::init(uint64_t stop,
uint64_t l1CacheSize,
uint64_t maxPrime)
{
ASSERT((maxPrime / 30) * getMaxFactor() + getMaxFactor() <= SievingPrime::MAX_MULTIPLEINDEX);
static_assert(config::FACTOR_ERATSMALL <= 4.5,
"config::FACTOR_ERATSMALL > 4.5 causes multipleIndex overflow 23-bits!");
stop_ = stop;
maxPrime_ = maxPrime;
l1CacheSize_ = (std::size_t) l1CacheSize;
std::size_t count = primeCountUpper(maxPrime);
primes_.reserve(count);
}
void EratSmall::storeSievingPrime(uint64_t prime,
uint64_t multipleIndex,
uint64_t wheelIndex)
{
ASSERT(prime <= maxPrime_);
uint64_t sievingPrime = prime / 30;
primes_.emplace_back(sievingPrime, multipleIndex, wheelIndex);
}
void EratSmall::crossOff(Vector<uint64_t>& sieve)
{
uint8_t* sieve8 = (uint8_t*) sieve.data();
std::size_t sieveBytes = sieve.size() * sizeof(uint64_t);
for (std::size_t i = 0; i < sieveBytes; i += l1CacheSize_)
{
std::size_t chunkSize = std::min(l1CacheSize_, sieveBytes - i);
crossOff(&sieve8[i], chunkSize);
}
}
void EratSmall::crossOff(uint8_t* sieve, std::size_t sieveBytes)
{
#define CHECK_FINISHED(wheelIndex) \
if (i >= sieveBytes) \
{ \
std::size_t multipleIndex = i - sieveBytes; \
prime.set(multipleIndex, wheelIndex); \
goto next_iteration; \
}
for (auto& prime : primes_)
{
std::size_t sievingPrime = prime.getSievingPrime();
std::size_t i = prime.getMultipleIndex();
std::size_t wheelIndex = prime.getWheelIndex();
ASSERT(wheelIndex <= 63);
switch (wheelIndex)
{
for (;;)
{
case 0: {
std::size_t maxOffset = sievingPrime * 28 + 6;
std::size_t limit = std::max(sieveBytes, maxOffset) - maxOffset;
for (; i < limit; i += sievingPrime * 30 + 7)
{
sieve[i + sievingPrime *  0 + 0] &= BIT0;
sieve[i + sievingPrime *  6 + 1] &= BIT4;
sieve[i + sievingPrime * 10 + 2] &= BIT3;
sieve[i + sievingPrime * 12 + 2] &= BIT7;
sieve[i + sievingPrime * 16 + 3] &= BIT6;
sieve[i + sievingPrime * 18 + 4] &= BIT2;
sieve[i + sievingPrime * 22 + 5] &= BIT1;
sieve[i + sievingPrime * 28 + 6] &= BIT5;
}
}
CHECK_FINISHED(0); sieve[i] &= BIT0; i += sievingPrime * 6 + 1; FALLTHROUGH;
case 1: CHECK_FINISHED(1); sieve[i] &= BIT4; i += sievingPrime * 4 + 1; FALLTHROUGH;
case 2: CHECK_FINISHED(2); sieve[i] &= BIT3; i += sievingPrime * 2 + 0; FALLTHROUGH;
case 3: CHECK_FINISHED(3); sieve[i] &= BIT7; i += sievingPrime * 4 + 1; FALLTHROUGH;
case 4: CHECK_FINISHED(4); sieve[i] &= BIT6; i += sievingPrime * 2 + 1; FALLTHROUGH;
case 5: CHECK_FINISHED(5); sieve[i] &= BIT2; i += sievingPrime * 4 + 1; FALLTHROUGH;
case 6: CHECK_FINISHED(6); sieve[i] &= BIT1; i += sievingPrime * 6 + 1; FALLTHROUGH;
case 7: CHECK_FINISHED(7); sieve[i] &= BIT5; i += sievingPrime * 2 + 1;
}
for (;;)
{
case  8: {
std::size_t maxOffset = sievingPrime * 28 + 10;
std::size_t limit = std::max(sieveBytes, maxOffset) - maxOffset;
for (; i < limit; i += sievingPrime * 30 + 11)
{
sieve[i + sievingPrime *  0 +  0] &= BIT1;
sieve[i + sievingPrime *  6 +  2] &= BIT3;
sieve[i + sievingPrime * 10 +  3] &= BIT7;
sieve[i + sievingPrime * 12 +  4] &= BIT5;
sieve[i + sievingPrime * 16 +  6] &= BIT0;
sieve[i + sievingPrime * 18 +  6] &= BIT6;
sieve[i + sievingPrime * 22 +  8] &= BIT2;
sieve[i + sievingPrime * 28 + 10] &= BIT4;
}
}
CHECK_FINISHED( 8); sieve[i] &= BIT1; i += sievingPrime * 6 + 2; FALLTHROUGH;
case  9: CHECK_FINISHED( 9); sieve[i] &= BIT3; i += sievingPrime * 4 + 1; FALLTHROUGH;
case 10: CHECK_FINISHED(10); sieve[i] &= BIT7; i += sievingPrime * 2 + 1; FALLTHROUGH;
case 11: CHECK_FINISHED(11); sieve[i] &= BIT5; i += sievingPrime * 4 + 2; FALLTHROUGH;
case 12: CHECK_FINISHED(12); sieve[i] &= BIT0; i += sievingPrime * 2 + 0; FALLTHROUGH;
case 13: CHECK_FINISHED(13); sieve[i] &= BIT6; i += sievingPrime * 4 + 2; FALLTHROUGH;
case 14: CHECK_FINISHED(14); sieve[i] &= BIT2; i += sievingPrime * 6 + 2; FALLTHROUGH;
case 15: CHECK_FINISHED(15); sieve[i] &= BIT4; i += sievingPrime * 2 + 1;
}
for (;;)
{
case 16: {
std::size_t maxOffset = sievingPrime * 28 + 12;
std::size_t limit = std::max(sieveBytes, maxOffset) - maxOffset;
for (; i < limit; i += sievingPrime * 30 + 13)
{
sieve[i + sievingPrime *  0 +  0] &= BIT2;
sieve[i + sievingPrime *  6 +  2] &= BIT7;
sieve[i + sievingPrime * 10 +  4] &= BIT5;
sieve[i + sievingPrime * 12 +  5] &= BIT4;
sieve[i + sievingPrime * 16 +  7] &= BIT1;
sieve[i + sievingPrime * 18 +  8] &= BIT0;
sieve[i + sievingPrime * 22 +  9] &= BIT6;
sieve[i + sievingPrime * 28 + 12] &= BIT3;
}
}
CHECK_FINISHED(16); sieve[i] &= BIT2; i += sievingPrime * 6 + 2; FALLTHROUGH;
case 17: CHECK_FINISHED(17); sieve[i] &= BIT7; i += sievingPrime * 4 + 2; FALLTHROUGH;
case 18: CHECK_FINISHED(18); sieve[i] &= BIT5; i += sievingPrime * 2 + 1; FALLTHROUGH;
case 19: CHECK_FINISHED(19); sieve[i] &= BIT4; i += sievingPrime * 4 + 2; FALLTHROUGH;
case 20: CHECK_FINISHED(20); sieve[i] &= BIT1; i += sievingPrime * 2 + 1; FALLTHROUGH;
case 21: CHECK_FINISHED(21); sieve[i] &= BIT0; i += sievingPrime * 4 + 1; FALLTHROUGH;
case 22: CHECK_FINISHED(22); sieve[i] &= BIT6; i += sievingPrime * 6 + 3; FALLTHROUGH;
case 23: CHECK_FINISHED(23); sieve[i] &= BIT3; i += sievingPrime * 2 + 1;
}
for (;;)
{
case 24: {
std::size_t maxOffset = sievingPrime * 28 + 16;
std::size_t limit = std::max(sieveBytes, maxOffset) - maxOffset;
for (; i < limit; i += sievingPrime * 30 + 17)
{
sieve[i + sievingPrime *  0 +  0] &= BIT3;
sieve[i + sievingPrime *  6 +  3] &= BIT6;
sieve[i + sievingPrime * 10 +  6] &= BIT0;
sieve[i + sievingPrime * 12 +  7] &= BIT1;
sieve[i + sievingPrime * 16 +  9] &= BIT4;
sieve[i + sievingPrime * 18 + 10] &= BIT5;
sieve[i + sievingPrime * 22 + 12] &= BIT7;
sieve[i + sievingPrime * 28 + 16] &= BIT2;
}
}
CHECK_FINISHED(24); sieve[i] &= BIT3; i += sievingPrime * 6 + 3; FALLTHROUGH;
case 25: CHECK_FINISHED(25); sieve[i] &= BIT6; i += sievingPrime * 4 + 3; FALLTHROUGH;
case 26: CHECK_FINISHED(26); sieve[i] &= BIT0; i += sievingPrime * 2 + 1; FALLTHROUGH;
case 27: CHECK_FINISHED(27); sieve[i] &= BIT1; i += sievingPrime * 4 + 2; FALLTHROUGH;
case 28: CHECK_FINISHED(28); sieve[i] &= BIT4; i += sievingPrime * 2 + 1; FALLTHROUGH;
case 29: CHECK_FINISHED(29); sieve[i] &= BIT5; i += sievingPrime * 4 + 2; FALLTHROUGH;
case 30: CHECK_FINISHED(30); sieve[i] &= BIT7; i += sievingPrime * 6 + 4; FALLTHROUGH;
case 31: CHECK_FINISHED(31); sieve[i] &= BIT2; i += sievingPrime * 2 + 1;
}
for (;;)
{
case 32: {
std::size_t maxOffset = sievingPrime * 28 + 18;
std::size_t limit = std::max(sieveBytes, maxOffset) - maxOffset;
for (; i < limit; i += sievingPrime * 30 + 19)
{
sieve[i + sievingPrime *  0 +  0] &= BIT4;
sieve[i + sievingPrime *  6 +  4] &= BIT2;
sieve[i + sievingPrime * 10 +  6] &= BIT6;
sieve[i + sievingPrime * 12 +  8] &= BIT0;
sieve[i + sievingPrime * 16 + 10] &= BIT5;
sieve[i + sievingPrime * 18 + 11] &= BIT7;
sieve[i + sievingPrime * 22 + 14] &= BIT3;
sieve[i + sievingPrime * 28 + 18] &= BIT1;
}
}
CHECK_FINISHED(32); sieve[i] &= BIT4; i += sievingPrime * 6 + 4; FALLTHROUGH;
case 33: CHECK_FINISHED(33); sieve[i] &= BIT2; i += sievingPrime * 4 + 2; FALLTHROUGH;
case 34: CHECK_FINISHED(34); sieve[i] &= BIT6; i += sievingPrime * 2 + 2; FALLTHROUGH;
case 35: CHECK_FINISHED(35); sieve[i] &= BIT0; i += sievingPrime * 4 + 2; FALLTHROUGH;
case 36: CHECK_FINISHED(36); sieve[i] &= BIT5; i += sievingPrime * 2 + 1; FALLTHROUGH;
case 37: CHECK_FINISHED(37); sieve[i] &= BIT7; i += sievingPrime * 4 + 3; FALLTHROUGH;
case 38: CHECK_FINISHED(38); sieve[i] &= BIT3; i += sievingPrime * 6 + 4; FALLTHROUGH;
case 39: CHECK_FINISHED(39); sieve[i] &= BIT1; i += sievingPrime * 2 + 1;
}
for (;;)
{
case 40: {
std::size_t maxOffset = sievingPrime * 28 + 22;
std::size_t limit = std::max(sieveBytes, maxOffset) - maxOffset;
for (; i < limit; i += sievingPrime * 30 + 23)
{
sieve[i + sievingPrime *  0 +  0] &= BIT5;
sieve[i + sievingPrime *  6 +  5] &= BIT1;
sieve[i + sievingPrime * 10 +  8] &= BIT2;
sieve[i + sievingPrime * 12 +  9] &= BIT6;
sieve[i + sievingPrime * 16 + 12] &= BIT7;
sieve[i + sievingPrime * 18 + 14] &= BIT3;
sieve[i + sievingPrime * 22 + 17] &= BIT4;
sieve[i + sievingPrime * 28 + 22] &= BIT0;
}
}
CHECK_FINISHED(40); sieve[i] &= BIT5; i += sievingPrime * 6 + 5; FALLTHROUGH;
case 41: CHECK_FINISHED(41); sieve[i] &= BIT1; i += sievingPrime * 4 + 3; FALLTHROUGH;
case 42: CHECK_FINISHED(42); sieve[i] &= BIT2; i += sievingPrime * 2 + 1; FALLTHROUGH;
case 43: CHECK_FINISHED(43); sieve[i] &= BIT6; i += sievingPrime * 4 + 3; FALLTHROUGH;
case 44: CHECK_FINISHED(44); sieve[i] &= BIT7; i += sievingPrime * 2 + 2; FALLTHROUGH;
case 45: CHECK_FINISHED(45); sieve[i] &= BIT3; i += sievingPrime * 4 + 3; FALLTHROUGH;
case 46: CHECK_FINISHED(46); sieve[i] &= BIT4; i += sievingPrime * 6 + 5; FALLTHROUGH;
case 47: CHECK_FINISHED(47); sieve[i] &= BIT0; i += sievingPrime * 2 + 1;
}
for (;;)
{
case 48: {
std::size_t maxOffset = sievingPrime * 28 + 27;
std::size_t limit = std::max(sieveBytes, maxOffset) - maxOffset;
for (; i < limit; i += sievingPrime * 30 + 29)
{
sieve[i + sievingPrime *  0 +  0] &= BIT6;
sieve[i + sievingPrime *  6 +  6] &= BIT5;
sieve[i + sievingPrime * 10 + 10] &= BIT4;
sieve[i + sievingPrime * 12 + 12] &= BIT3;
sieve[i + sievingPrime * 16 + 16] &= BIT2;
sieve[i + sievingPrime * 18 + 18] &= BIT1;
sieve[i + sievingPrime * 22 + 22] &= BIT0;
sieve[i + sievingPrime * 28 + 27] &= BIT7;
}
}
CHECK_FINISHED(48); sieve[i] &= BIT6; i += sievingPrime * 6 + 6; FALLTHROUGH;
case 49: CHECK_FINISHED(49); sieve[i] &= BIT5; i += sievingPrime * 4 + 4; FALLTHROUGH;
case 50: CHECK_FINISHED(50); sieve[i] &= BIT4; i += sievingPrime * 2 + 2; FALLTHROUGH;
case 51: CHECK_FINISHED(51); sieve[i] &= BIT3; i += sievingPrime * 4 + 4; FALLTHROUGH;
case 52: CHECK_FINISHED(52); sieve[i] &= BIT2; i += sievingPrime * 2 + 2; FALLTHROUGH;
case 53: CHECK_FINISHED(53); sieve[i] &= BIT1; i += sievingPrime * 4 + 4; FALLTHROUGH;
case 54: CHECK_FINISHED(54); sieve[i] &= BIT0; i += sievingPrime * 6 + 5; FALLTHROUGH;
case 55: CHECK_FINISHED(55); sieve[i] &= BIT7; i += sievingPrime * 2 + 2;
}
for (;;)
{
case 56: {
std::size_t maxOffset = sievingPrime * 28 + 1;
std::size_t limit = std::max(sieveBytes, maxOffset) - maxOffset;
for (; i < limit; i += sievingPrime * 30 + 1)
{
sieve[i + sievingPrime *  0 + 0] &= BIT7;
sieve[i + sievingPrime *  6 + 1] &= BIT0;
sieve[i + sievingPrime * 10 + 1] &= BIT1;
sieve[i + sievingPrime * 12 + 1] &= BIT2;
sieve[i + sievingPrime * 16 + 1] &= BIT3;
sieve[i + sievingPrime * 18 + 1] &= BIT4;
sieve[i + sievingPrime * 22 + 1] &= BIT5;
sieve[i + sievingPrime * 28 + 1] &= BIT6;
}
}
CHECK_FINISHED(56); sieve[i] &= BIT7; i += sievingPrime * 6 + 1; FALLTHROUGH;
case 57: CHECK_FINISHED(57); sieve[i] &= BIT0; i += sievingPrime * 4 + 0; FALLTHROUGH;
case 58: CHECK_FINISHED(58); sieve[i] &= BIT1; i += sievingPrime * 2 + 0; FALLTHROUGH;
case 59: CHECK_FINISHED(59); sieve[i] &= BIT2; i += sievingPrime * 4 + 0; FALLTHROUGH;
case 60: CHECK_FINISHED(60); sieve[i] &= BIT3; i += sievingPrime * 2 + 0; FALLTHROUGH;
case 61: CHECK_FINISHED(61); sieve[i] &= BIT4; i += sievingPrime * 4 + 0; FALLTHROUGH;
case 62: CHECK_FINISHED(62); sieve[i] &= BIT5; i += sievingPrime * 6 + 0; FALLTHROUGH;
case 63: CHECK_FINISHED(63); sieve[i] &= BIT6; i += sievingPrime * 2 + 0;
}
default: UNREACHABLE;
}
next_iteration:;
}
}
} 

#undef CHECK_FINISHED

#ifndef ERATMEDIUM_HPP
#define ERATMEDIUM_HPP
#include <stdint.h>
namespace primesieve {
class MemoryPool;
class SievingPrime;
class Bucket;
class EratMedium : public Wheel30_t
{
public:
void init(uint64_t, uint64_t, MemoryPool&);
bool hasSievingPrimes() const { return !buckets_.empty(); }
NOINLINE void crossOff(Vector<uint64_t>& sieve);
public: // adaptation: expose relative-state insertion
uint64_t maxPrime_ = 0;
MemoryPool* memoryPool_ = nullptr;
Vector<SievingPrime*> buckets_;
Vector<SievingPrime*> currentBuckets_;
void storeSievingPrime(uint64_t, uint64_t, uint64_t);
NOINLINE void crossOff_7(uint8_t*, std::size_t, Bucket*);
NOINLINE void crossOff_11(uint8_t*, std::size_t, Bucket*);
NOINLINE void crossOff_13(uint8_t*, std::size_t, Bucket*);
NOINLINE void crossOff_17(uint8_t*, std::size_t, Bucket*);
NOINLINE void crossOff_19(uint8_t*, std::size_t, Bucket*);
NOINLINE void crossOff_23(uint8_t*, std::size_t, Bucket*);
NOINLINE void crossOff_29(uint8_t*, std::size_t, Bucket*);
NOINLINE void crossOff_31(uint8_t*, std::size_t, Bucket*);
};
} 
#endif
#include <stdint.h>
namespace primesieve {
void EratMedium::init(uint64_t stop,
uint64_t maxPrime,
MemoryPool& memoryPool)
{
ASSERT((maxPrime / 30) * getMaxFactor() + getMaxFactor() <= SievingPrime::MAX_MULTIPLEINDEX);
static_assert(config::FACTOR_ERATMEDIUM <= 4.5,
"config::FACTOR_ERATMEDIUM > 4.5 causes multipleIndex overflow 23-bits!");
stop_ = stop;
maxPrime_ = maxPrime;
memoryPool_ = &memoryPool;
}
void EratMedium::storeSievingPrime(uint64_t prime,
uint64_t multipleIndex,
uint64_t wheelIndex)
{
ASSERT(prime <= maxPrime_);
uint64_t sievingPrime = prime / 30;
if_unlikely(buckets_.empty())
{
buckets_.resize(64);
currentBuckets_.resize(64);
std::fill_n(buckets_.begin(), 64, nullptr);
std::fill_n(currentBuckets_.begin(), 64, nullptr);
}
if (Bucket::isFull(buckets_[wheelIndex]))
memoryPool_->addBucket(buckets_[wheelIndex]);
buckets_[wheelIndex]++->set(sievingPrime, multipleIndex, wheelIndex);
}
void EratMedium::crossOff(Vector<uint64_t>& sieve)
{
currentBuckets_.swap(buckets_);
uint8_t* sieve8 = (uint8_t*) sieve.data();
std::size_t sieveBytes = sieve.size() * sizeof(uint64_t);
for (std::size_t i = 0; i < 64; i++)
{
if (currentBuckets_[i])
{
Bucket* bucket = Bucket::get(currentBuckets_[i]);
bucket->setEnd(currentBuckets_[i]);
currentBuckets_[i] = nullptr;
std::size_t wheelIndex = i;
while (bucket)
{
switch (wheelIndex / 8)
{
case 0: crossOff_7 (sieve8, sieveBytes, bucket); break;
case 1: crossOff_11(sieve8, sieveBytes, bucket); break;
case 2: crossOff_13(sieve8, sieveBytes, bucket); break;
case 3: crossOff_17(sieve8, sieveBytes, bucket); break;
case 4: crossOff_19(sieve8, sieveBytes, bucket); break;
case 5: crossOff_23(sieve8, sieveBytes, bucket); break;
case 6: crossOff_29(sieve8, sieveBytes, bucket); break;
case 7: crossOff_31(sieve8, sieveBytes, bucket); break;
default: UNREACHABLE;
}
Bucket* processed = bucket;
bucket = bucket->next();
memoryPool_->freeBucket(processed);
}
}
}
}
#define CHECK_FINISHED(wheelIndex) \
if_unlikely(i >= sieveBytes) \
{ \
i -= sieveBytes; \
if (Bucket::isFull(buckets[wheelIndex])) \
memoryPool.addBucket(buckets[wheelIndex]); \
buckets[wheelIndex]++->set(sievingPrime, i, wheelIndex); \
break; \
}
void EratMedium::crossOff_7(uint8_t* sieve, std::size_t sieveBytes, Bucket* bucket)
{
auto buckets = buckets_.data();
MemoryPool& memoryPool = *memoryPool_;
SievingPrime* prime = bucket->begin();
SievingPrime* end = bucket->end();
std::size_t wheelIndex = prime->getWheelIndex();
for (; prime != end; prime++)
{
std::size_t sievingPrime = prime->getSievingPrime();
std::size_t i = prime->getMultipleIndex();
std::size_t dist0 = sievingPrime * 6 + 1;
std::size_t dist1 = sievingPrime * 4 + 1;
std::size_t dist2 = sievingPrime * 2 + 0;
std::size_t dist4 = sievingPrime * 2 + 1;
ASSERT(wheelIndex <= 7);
switch (wheelIndex)
{
default: UNREACHABLE;
for (;;)
{
case 0: CHECK_FINISHED(0); sieve[i] &= BIT0; i += dist0; FALLTHROUGH;
case 1: CHECK_FINISHED(1); sieve[i] &= BIT4; i += dist1; FALLTHROUGH;
case 2: CHECK_FINISHED(2); sieve[i] &= BIT3; i += dist2; FALLTHROUGH;
case 3: CHECK_FINISHED(3); sieve[i] &= BIT7; i += dist1; FALLTHROUGH;
case 4: CHECK_FINISHED(4); sieve[i] &= BIT6; i += dist4; FALLTHROUGH;
case 5: CHECK_FINISHED(5); sieve[i] &= BIT2; i += dist1; FALLTHROUGH;
case 6: CHECK_FINISHED(6); sieve[i] &= BIT1; i += dist0; FALLTHROUGH;
case 7: CHECK_FINISHED(7); sieve[i] &= BIT5; i += dist4;
}
}
}
}
void EratMedium::crossOff_11(uint8_t* sieve, std::size_t sieveBytes, Bucket* bucket)
{
auto buckets = buckets_.data();
MemoryPool& memoryPool = *memoryPool_;
SievingPrime* prime = bucket->begin();
SievingPrime* end = bucket->end();
std::size_t wheelIndex = prime->getWheelIndex();
for (; prime != end; prime++)
{
std::size_t sievingPrime = prime->getSievingPrime();
std::size_t i = prime->getMultipleIndex();
std::size_t dist0 = sievingPrime * 6 + 2;
std::size_t dist1 = sievingPrime * 4 + 1;
std::size_t dist2 = sievingPrime * 2 + 1;
std::size_t dist3 = sievingPrime * 4 + 2;
std::size_t dist4 = sievingPrime * 2 + 0;
ASSERT(wheelIndex >= 8);
ASSERT(wheelIndex <= 15);
switch (wheelIndex)
{
default: UNREACHABLE;
for (;;)
{
case  8: CHECK_FINISHED( 8); sieve[i] &= BIT1; i += dist0; FALLTHROUGH;
case  9: CHECK_FINISHED( 9); sieve[i] &= BIT3; i += dist1; FALLTHROUGH;
case 10: CHECK_FINISHED(10); sieve[i] &= BIT7; i += dist2; FALLTHROUGH;
case 11: CHECK_FINISHED(11); sieve[i] &= BIT5; i += dist3; FALLTHROUGH;
case 12: CHECK_FINISHED(12); sieve[i] &= BIT0; i += dist4; FALLTHROUGH;
case 13: CHECK_FINISHED(13); sieve[i] &= BIT6; i += dist3; FALLTHROUGH;
case 14: CHECK_FINISHED(14); sieve[i] &= BIT2; i += dist0; FALLTHROUGH;
case 15: CHECK_FINISHED(15); sieve[i] &= BIT4; i += dist2;
}
}
}
}
void EratMedium::crossOff_13(uint8_t* sieve, std::size_t sieveBytes, Bucket* bucket)
{
auto buckets = buckets_.data();
MemoryPool& memoryPool = *memoryPool_;
SievingPrime* prime = bucket->begin();
SievingPrime* end = bucket->end();
std::size_t wheelIndex = prime->getWheelIndex();
for (; prime != end; prime++)
{
std::size_t sievingPrime = prime->getSievingPrime();
std::size_t i = prime->getMultipleIndex();
std::size_t dist0 = sievingPrime * 6 + 2;
std::size_t dist1 = sievingPrime * 4 + 2;
std::size_t dist2 = sievingPrime * 2 + 1;
std::size_t dist5 = sievingPrime * 4 + 1;
std::size_t dist6 = sievingPrime * 6 + 3;
ASSERT(wheelIndex >= 16);
ASSERT(wheelIndex <= 23);
switch (wheelIndex)
{
default: UNREACHABLE;
for (;;)
{
case 16: CHECK_FINISHED(16); sieve[i] &= BIT2; i += dist0; FALLTHROUGH;
case 17: CHECK_FINISHED(17); sieve[i] &= BIT7; i += dist1; FALLTHROUGH;
case 18: CHECK_FINISHED(18); sieve[i] &= BIT5; i += dist2; FALLTHROUGH;
case 19: CHECK_FINISHED(19); sieve[i] &= BIT4; i += dist1; FALLTHROUGH;
case 20: CHECK_FINISHED(20); sieve[i] &= BIT1; i += dist2; FALLTHROUGH;
case 21: CHECK_FINISHED(21); sieve[i] &= BIT0; i += dist5; FALLTHROUGH;
case 22: CHECK_FINISHED(22); sieve[i] &= BIT6; i += dist6; FALLTHROUGH;
case 23: CHECK_FINISHED(23); sieve[i] &= BIT3; i += dist2;
}
}
}
}
void EratMedium::crossOff_17(uint8_t* sieve, std::size_t sieveBytes, Bucket* bucket)
{
auto buckets = buckets_.data();
MemoryPool& memoryPool = *memoryPool_;
SievingPrime* prime = bucket->begin();
SievingPrime* end = bucket->end();
std::size_t wheelIndex = prime->getWheelIndex();
for (; prime != end; prime++)
{
std::size_t sievingPrime = prime->getSievingPrime();
std::size_t i = prime->getMultipleIndex();
std::size_t dist0 = sievingPrime * 6 + 3;
std::size_t dist1 = sievingPrime * 4 + 3;
std::size_t dist2 = sievingPrime * 2 + 1;
std::size_t dist3 = sievingPrime * 4 + 2;
std::size_t dist6 = sievingPrime * 6 + 4;
ASSERT(wheelIndex >= 24);
ASSERT(wheelIndex <= 31);
switch (wheelIndex)
{
default: UNREACHABLE;
for (;;)
{
case 24: CHECK_FINISHED(24); sieve[i] &= BIT3; i += dist0; FALLTHROUGH;
case 25: CHECK_FINISHED(25); sieve[i] &= BIT6; i += dist1; FALLTHROUGH;
case 26: CHECK_FINISHED(26); sieve[i] &= BIT0; i += dist2; FALLTHROUGH;
case 27: CHECK_FINISHED(27); sieve[i] &= BIT1; i += dist3; FALLTHROUGH;
case 28: CHECK_FINISHED(28); sieve[i] &= BIT4; i += dist2; FALLTHROUGH;
case 29: CHECK_FINISHED(29); sieve[i] &= BIT5; i += dist3; FALLTHROUGH;
case 30: CHECK_FINISHED(30); sieve[i] &= BIT7; i += dist6; FALLTHROUGH;
case 31: CHECK_FINISHED(31); sieve[i] &= BIT2; i += dist2;
}
}
}
}
void EratMedium::crossOff_19(uint8_t* sieve, std::size_t sieveBytes, Bucket* bucket)
{
auto buckets = buckets_.data();
MemoryPool& memoryPool = *memoryPool_;
SievingPrime* prime = bucket->begin();
SievingPrime* end = bucket->end();
std::size_t wheelIndex = prime->getWheelIndex();
for (; prime != end; prime++)
{
std::size_t sievingPrime = prime->getSievingPrime();
std::size_t i = prime->getMultipleIndex();
std::size_t dist0 = sievingPrime * 6 + 4;
std::size_t dist1 = sievingPrime * 4 + 2;
std::size_t dist2 = sievingPrime * 2 + 2;
std::size_t dist4 = sievingPrime * 2 + 1;
std::size_t dist5 = sievingPrime * 4 + 3;
ASSERT(wheelIndex >= 32);
ASSERT(wheelIndex <= 39);
switch (wheelIndex)
{
default: UNREACHABLE;
for (;;)
{
case 32: CHECK_FINISHED(32); sieve[i] &= BIT4; i += dist0; FALLTHROUGH;
case 33: CHECK_FINISHED(33); sieve[i] &= BIT2; i += dist1; FALLTHROUGH;
case 34: CHECK_FINISHED(34); sieve[i] &= BIT6; i += dist2; FALLTHROUGH;
case 35: CHECK_FINISHED(35); sieve[i] &= BIT0; i += dist1; FALLTHROUGH;
case 36: CHECK_FINISHED(36); sieve[i] &= BIT5; i += dist4; FALLTHROUGH;
case 37: CHECK_FINISHED(37); sieve[i] &= BIT7; i += dist5; FALLTHROUGH;
case 38: CHECK_FINISHED(38); sieve[i] &= BIT3; i += dist0; FALLTHROUGH;
case 39: CHECK_FINISHED(39); sieve[i] &= BIT1; i += dist4;
}
}
}
}
void EratMedium::crossOff_23(uint8_t* sieve, std::size_t sieveBytes, Bucket* bucket)
{
auto buckets = buckets_.data();
MemoryPool& memoryPool = *memoryPool_;
SievingPrime* prime = bucket->begin();
SievingPrime* end = bucket->end();
std::size_t wheelIndex = prime->getWheelIndex();
for (; prime != end; prime++)
{
std::size_t sievingPrime = prime->getSievingPrime();
std::size_t i = prime->getMultipleIndex();
std::size_t dist0 = sievingPrime * 6 + 5;
std::size_t dist1 = sievingPrime * 4 + 3;
std::size_t dist2 = sievingPrime * 2 + 1;
std::size_t dist4 = sievingPrime * 2 + 2;
ASSERT(wheelIndex >= 40);
ASSERT(wheelIndex <= 47);
switch (wheelIndex)
{
default: UNREACHABLE;
for (;;)
{
case 40: CHECK_FINISHED(40); sieve[i] &= BIT5; i += dist0; FALLTHROUGH;
case 41: CHECK_FINISHED(41); sieve[i] &= BIT1; i += dist1; FALLTHROUGH;
case 42: CHECK_FINISHED(42); sieve[i] &= BIT2; i += dist2; FALLTHROUGH;
case 43: CHECK_FINISHED(43); sieve[i] &= BIT6; i += dist1; FALLTHROUGH;
case 44: CHECK_FINISHED(44); sieve[i] &= BIT7; i += dist4; FALLTHROUGH;
case 45: CHECK_FINISHED(45); sieve[i] &= BIT3; i += dist1; FALLTHROUGH;
case 46: CHECK_FINISHED(46); sieve[i] &= BIT4; i += dist0; FALLTHROUGH;
case 47: CHECK_FINISHED(47); sieve[i] &= BIT0; i += dist2;
}
}
}
}
void EratMedium::crossOff_29(uint8_t* sieve, std::size_t sieveBytes, Bucket* bucket)
{
auto buckets = buckets_.data();
MemoryPool& memoryPool = *memoryPool_;
SievingPrime* prime = bucket->begin();
SievingPrime* end = bucket->end();
std::size_t wheelIndex = prime->getWheelIndex();
for (; prime != end; prime++)
{
std::size_t sievingPrime = prime->getSievingPrime();
std::size_t i = prime->getMultipleIndex();
std::size_t dist0 = sievingPrime * 6 + 6;
std::size_t dist1 = sievingPrime * 4 + 4;
std::size_t dist2 = sievingPrime * 2 + 2;
std::size_t dist6 = sievingPrime * 6 + 5;
ASSERT(wheelIndex >= 48);
ASSERT(wheelIndex <= 55);
switch (wheelIndex)
{
default: UNREACHABLE;
for (;;)
{
case 48: CHECK_FINISHED(48); sieve[i] &= BIT6; i += dist0; FALLTHROUGH;
case 49: CHECK_FINISHED(49); sieve[i] &= BIT5; i += dist1; FALLTHROUGH;
case 50: CHECK_FINISHED(50); sieve[i] &= BIT4; i += dist2; FALLTHROUGH;
case 51: CHECK_FINISHED(51); sieve[i] &= BIT3; i += dist1; FALLTHROUGH;
case 52: CHECK_FINISHED(52); sieve[i] &= BIT2; i += dist2; FALLTHROUGH;
case 53: CHECK_FINISHED(53); sieve[i] &= BIT1; i += dist1; FALLTHROUGH;
case 54: CHECK_FINISHED(54); sieve[i] &= BIT0; i += dist6; FALLTHROUGH;
case 55: CHECK_FINISHED(55); sieve[i] &= BIT7; i += dist2;
}
}
}
}
void EratMedium::crossOff_31(uint8_t* sieve, std::size_t sieveBytes, Bucket* bucket)
{
auto buckets = buckets_.data();
MemoryPool& memoryPool = *memoryPool_;
SievingPrime* prime = bucket->begin();
SievingPrime* end = bucket->end();
std::size_t wheelIndex = prime->getWheelIndex();
for (; prime != end; prime++)
{
std::size_t sievingPrime = prime->getSievingPrime();
std::size_t i = prime->getMultipleIndex();
std::size_t dist0 = sievingPrime * 6 + 1;
std::size_t dist1 = sievingPrime * 4 + 0;
std::size_t dist2 = sievingPrime * 2 + 0;
std::size_t dist6 = sievingPrime * 6 + 0;
ASSERT(wheelIndex >= 56);
ASSERT(wheelIndex <= 63);
switch (wheelIndex)
{
default: UNREACHABLE;
for (;;)
{
case 56: CHECK_FINISHED(56); sieve[i] &= BIT7; i += dist0; FALLTHROUGH;
case 57: CHECK_FINISHED(57); sieve[i] &= BIT0; i += dist1; FALLTHROUGH;
case 58: CHECK_FINISHED(58); sieve[i] &= BIT1; i += dist2; FALLTHROUGH;
case 59: CHECK_FINISHED(59); sieve[i] &= BIT2; i += dist1; FALLTHROUGH;
case 60: CHECK_FINISHED(60); sieve[i] &= BIT3; i += dist2; FALLTHROUGH;
case 61: CHECK_FINISHED(61); sieve[i] &= BIT4; i += dist1; FALLTHROUGH;
case 62: CHECK_FINISHED(62); sieve[i] &= BIT5; i += dist6; FALLTHROUGH;
case 63: CHECK_FINISHED(63); sieve[i] &= BIT6; i += dist2;
}
}
}
}
} 

#undef CHECK_FINISHED

#ifndef ERATBIG_HPP
#define ERATBIG_HPP
#include <stdint.h>
namespace primesieve {
class MemoryPool;
class SievingPrime;
class EratBig : public Wheel210_t
{
public:
void init(uint64_t stop, uint64_t maxPrime, const Vector<uint64_t>& sieve, MemoryPool&);
NOINLINE void crossOff(Vector<uint64_t>& sieve);
bool hasSievingPrimes() const { return !buckets_.empty(); }
public: // adaptation: expose relative-state insertion
uint64_t remainingBytes_ = uint64_t(-1);
uint64_t maxPrime_ = 0;
uint64_t log2SieveBytes_ = 0;
uint64_t moduloSieveBytes_ = 0;
MemoryPool* memoryPool_ = nullptr;
Vector<SievingPrime*> buckets_;
void storeSievingPrime(uint64_t, uint64_t, uint64_t);
NOINLINE void crossOff(uint8_t* sieve, SievingPrime* prime, SievingPrime* end);
};
} 
#endif
#include <stdint.h>
#include <algorithm>
namespace {
struct WheelElement
{
uint8_t unsetBit;
uint8_t nextMultipleFactor;
uint8_t correct;
uint32_t next;
};
static_assert(primesieve::isPow2(sizeof(WheelElement)),
"sizeof(WheelElement) must be a power of 2!");
const primesieve::Array<WheelElement, 8*48> wheel210 =
{{
{ BIT0, 10,  2,   1 }, { BIT3,  2,  0,   2 }, { BIT7,  4,  1,   3 }, { BIT6,  2,  1,   4 }, { BIT2,  4,  1,   5 }, { BIT1,  6,  1,   6 }, { BIT5,  2,  1,   7 }, { BIT0,  6,  1,   8 },
{ BIT4,  4,  1,   9 }, { BIT3,  2,  0,  10 }, { BIT7,  4,  1,  11 }, { BIT6,  6,  2,  12 }, { BIT1,  6,  1,  13 }, { BIT5,  2,  1,  14 }, { BIT0,  6,  1,  15 }, { BIT4,  4,  1,  16 },
{ BIT3,  2,  0,  17 }, { BIT7,  6,  2,  18 }, { BIT2,  4,  1,  19 }, { BIT1,  6,  1,  20 }, { BIT5,  8,  2,  21 }, { BIT4,  4,  1,  22 }, { BIT3,  2,  0,  23 }, { BIT7,  4,  1,  24 },
{ BIT6,  2,  1,  25 }, { BIT2,  4,  1,  26 }, { BIT1,  8,  2,  27 }, { BIT0,  6,  1,  28 }, { BIT4,  4,  1,  29 }, { BIT3,  6,  1,  30 }, { BIT6,  2,  1,  31 }, { BIT2,  4,  1,  32 },
{ BIT1,  6,  1,  33 }, { BIT5,  2,  1,  34 }, { BIT0,  6,  1,  35 }, { BIT4,  6,  1,  36 }, { BIT7,  4,  1,  37 }, { BIT6,  2,  1,  38 }, { BIT2,  4,  1,  39 }, { BIT1,  6,  1,  40 },
{ BIT5,  2,  1,  41 }, { BIT0,  6,  1,  42 }, { BIT4,  4,  1,  43 }, { BIT3,  2,  0,  44 }, { BIT7,  4,  1,  45 }, { BIT6,  2,  1,  46 }, { BIT2, 10,  2,  47 }, { BIT5,  2,  1,   0 },
{ BIT1, 10,  3,  49 }, { BIT7,  2,  1,  50 }, { BIT5,  4,  2,  51 }, { BIT0,  2,  0,  52 }, { BIT6,  4,  2,  53 }, { BIT2,  6,  2,  54 }, { BIT4,  2,  1,  55 }, { BIT1,  6,  2,  56 },
{ BIT3,  4,  1,  57 }, { BIT7,  2,  1,  58 }, { BIT5,  4,  2,  59 }, { BIT0,  6,  2,  60 }, { BIT2,  6,  2,  61 }, { BIT4,  2,  1,  62 }, { BIT1,  6,  2,  63 }, { BIT3,  4,  1,  64 },
{ BIT7,  2,  1,  65 }, { BIT5,  6,  2,  66 }, { BIT6,  4,  2,  67 }, { BIT2,  6,  2,  68 }, { BIT4,  8,  3,  69 }, { BIT3,  4,  1,  70 }, { BIT7,  2,  1,  71 }, { BIT5,  4,  2,  72 },
{ BIT0,  2,  0,  73 }, { BIT6,  4,  2,  74 }, { BIT2,  8,  3,  75 }, { BIT1,  6,  2,  76 }, { BIT3,  4,  1,  77 }, { BIT7,  6,  3,  78 }, { BIT0,  2,  0,  79 }, { BIT6,  4,  2,  80 },
{ BIT2,  6,  2,  81 }, { BIT4,  2,  1,  82 }, { BIT1,  6,  2,  83 }, { BIT3,  6,  2,  84 }, { BIT5,  4,  2,  85 }, { BIT0,  2,  0,  86 }, { BIT6,  4,  2,  87 }, { BIT2,  6,  2,  88 },
{ BIT4,  2,  1,  89 }, { BIT1,  6,  2,  90 }, { BIT3,  4,  1,  91 }, { BIT7,  2,  1,  92 }, { BIT5,  4,  2,  93 }, { BIT0,  2,  0,  94 }, { BIT6, 10,  4,  95 }, { BIT4,  2,  1,  48 },
{ BIT2, 10,  4,  97 }, { BIT5,  2,  1,  98 }, { BIT4,  4,  2,  99 }, { BIT1,  2,  1, 100 }, { BIT0,  4,  1, 101 }, { BIT6,  6,  3, 102 }, { BIT3,  2,  1, 103 }, { BIT2,  6,  2, 104 },
{ BIT7,  4,  2, 105 }, { BIT5,  2,  1, 106 }, { BIT4,  4,  2, 107 }, { BIT1,  6,  2, 108 }, { BIT6,  6,  3, 109 }, { BIT3,  2,  1, 110 }, { BIT2,  6,  2, 111 }, { BIT7,  4,  2, 112 },
{ BIT5,  2,  1, 113 }, { BIT4,  6,  3, 114 }, { BIT0,  4,  1, 115 }, { BIT6,  6,  3, 116 }, { BIT3,  8,  3, 117 }, { BIT7,  4,  2, 118 }, { BIT5,  2,  1, 119 }, { BIT4,  4,  2, 120 },
{ BIT1,  2,  1, 121 }, { BIT0,  4,  1, 122 }, { BIT6,  8,  4, 123 }, { BIT2,  6,  2, 124 }, { BIT7,  4,  2, 125 }, { BIT5,  6,  3, 126 }, { BIT1,  2,  1, 127 }, { BIT0,  4,  1, 128 },
{ BIT6,  6,  3, 129 }, { BIT3,  2,  1, 130 }, { BIT2,  6,  2, 131 }, { BIT7,  6,  3, 132 }, { BIT4,  4,  2, 133 }, { BIT1,  2,  1, 134 }, { BIT0,  4,  1, 135 }, { BIT6,  6,  3, 136 },
{ BIT3,  2,  1, 137 }, { BIT2,  6,  2, 138 }, { BIT7,  4,  2, 139 }, { BIT5,  2,  1, 140 }, { BIT4,  4,  2, 141 }, { BIT1,  2,  1, 142 }, { BIT0, 10,  4, 143 }, { BIT3,  2,  1,  96 },
{ BIT3, 10,  6, 145 }, { BIT0,  2,  1, 146 }, { BIT1,  4,  2, 147 }, { BIT4,  2,  1, 148 }, { BIT5,  4,  2, 149 }, { BIT7,  6,  4, 150 }, { BIT2,  2,  1, 151 }, { BIT3,  6,  3, 152 },
{ BIT6,  4,  3, 153 }, { BIT0,  2,  1, 154 }, { BIT1,  4,  2, 155 }, { BIT4,  6,  3, 156 }, { BIT7,  6,  4, 157 }, { BIT2,  2,  1, 158 }, { BIT3,  6,  3, 159 }, { BIT6,  4,  3, 160 },
{ BIT0,  2,  1, 161 }, { BIT1,  6,  3, 162 }, { BIT5,  4,  2, 163 }, { BIT7,  6,  4, 164 }, { BIT2,  8,  4, 165 }, { BIT6,  4,  3, 166 }, { BIT0,  2,  1, 167 }, { BIT1,  4,  2, 168 },
{ BIT4,  2,  1, 169 }, { BIT5,  4,  2, 170 }, { BIT7,  8,  5, 171 }, { BIT3,  6,  3, 172 }, { BIT6,  4,  3, 173 }, { BIT0,  6,  3, 174 }, { BIT4,  2,  1, 175 }, { BIT5,  4,  2, 176 },
{ BIT7,  6,  4, 177 }, { BIT2,  2,  1, 178 }, { BIT3,  6,  3, 179 }, { BIT6,  6,  4, 180 }, { BIT1,  4,  2, 181 }, { BIT4,  2,  1, 182 }, { BIT5,  4,  2, 183 }, { BIT7,  6,  4, 184 },
{ BIT2,  2,  1, 185 }, { BIT3,  6,  3, 186 }, { BIT6,  4,  3, 187 }, { BIT0,  2,  1, 188 }, { BIT1,  4,  2, 189 }, { BIT4,  2,  1, 190 }, { BIT5, 10,  6, 191 }, { BIT2,  2,  1, 144 },
{ BIT4, 10,  6, 193 }, { BIT6,  2,  2, 194 }, { BIT0,  4,  2, 195 }, { BIT5,  2,  1, 196 }, { BIT7,  4,  3, 197 }, { BIT3,  6,  4, 198 }, { BIT1,  2,  1, 199 }, { BIT4,  6,  4, 200 },
{ BIT2,  4,  2, 201 }, { BIT6,  2,  2, 202 }, { BIT0,  4,  2, 203 }, { BIT5,  6,  4, 204 }, { BIT3,  6,  4, 205 }, { BIT1,  2,  1, 206 }, { BIT4,  6,  4, 207 }, { BIT2,  4,  2, 208 },
{ BIT6,  2,  2, 209 }, { BIT0,  6,  3, 210 }, { BIT7,  4,  3, 211 }, { BIT3,  6,  4, 212 }, { BIT1,  8,  5, 213 }, { BIT2,  4,  2, 214 }, { BIT6,  2,  2, 215 }, { BIT0,  4,  2, 216 },
{ BIT5,  2,  1, 217 }, { BIT7,  4,  3, 218 }, { BIT3,  8,  5, 219 }, { BIT4,  6,  4, 220 }, { BIT2,  4,  2, 221 }, { BIT6,  6,  4, 222 }, { BIT5,  2,  1, 223 }, { BIT7,  4,  3, 224 },
{ BIT3,  6,  4, 225 }, { BIT1,  2,  1, 226 }, { BIT4,  6,  4, 227 }, { BIT2,  6,  4, 228 }, { BIT0,  4,  2, 229 }, { BIT5,  2,  1, 230 }, { BIT7,  4,  3, 231 }, { BIT3,  6,  4, 232 },
{ BIT1,  2,  1, 233 }, { BIT4,  6,  4, 234 }, { BIT2,  4,  2, 235 }, { BIT6,  2,  2, 236 }, { BIT0,  4,  2, 237 }, { BIT5,  2,  1, 238 }, { BIT7, 10,  7, 239 }, { BIT1,  2,  1, 192 },
{ BIT5, 10,  8, 241 }, { BIT2,  2,  1, 242 }, { BIT6,  4,  3, 243 }, { BIT7,  2,  2, 244 }, { BIT3,  4,  3, 245 }, { BIT4,  6,  5, 246 }, { BIT0,  2,  1, 247 }, { BIT5,  6,  5, 248 },
{ BIT1,  4,  3, 249 }, { BIT2,  2,  1, 250 }, { BIT6,  4,  3, 251 }, { BIT7,  6,  5, 252 }, { BIT4,  6,  5, 253 }, { BIT0,  2,  1, 254 }, { BIT5,  6,  5, 255 }, { BIT1,  4,  3, 256 },
{ BIT2,  2,  1, 257 }, { BIT6,  6,  5, 258 }, { BIT3,  4,  3, 259 }, { BIT4,  6,  5, 260 }, { BIT0,  8,  6, 261 }, { BIT1,  4,  3, 262 }, { BIT2,  2,  1, 263 }, { BIT6,  4,  3, 264 },
{ BIT7,  2,  2, 265 }, { BIT3,  4,  3, 266 }, { BIT4,  8,  6, 267 }, { BIT5,  6,  5, 268 }, { BIT1,  4,  3, 269 }, { BIT2,  6,  4, 270 }, { BIT7,  2,  2, 271 }, { BIT3,  4,  3, 272 },
{ BIT4,  6,  5, 273 }, { BIT0,  2,  1, 274 }, { BIT5,  6,  5, 275 }, { BIT1,  6,  4, 276 }, { BIT6,  4,  3, 277 }, { BIT7,  2,  2, 278 }, { BIT3,  4,  3, 279 }, { BIT4,  6,  5, 280 },
{ BIT0,  2,  1, 281 }, { BIT5,  6,  5, 282 }, { BIT1,  4,  3, 283 }, { BIT2,  2,  1, 284 }, { BIT6,  4,  3, 285 }, { BIT7,  2,  2, 286 }, { BIT3, 10,  8, 287 }, { BIT0,  2,  1, 240 },
{ BIT6, 10, 10, 289 }, { BIT4,  2,  2, 290 }, { BIT3,  4,  4, 291 }, { BIT2,  2,  2, 292 }, { BIT1,  4,  4, 293 }, { BIT0,  6,  5, 294 }, { BIT7,  2,  2, 295 }, { BIT6,  6,  6, 296 },
{ BIT5,  4,  4, 297 }, { BIT4,  2,  2, 298 }, { BIT3,  4,  4, 299 }, { BIT2,  6,  6, 300 }, { BIT0,  6,  5, 301 }, { BIT7,  2,  2, 302 }, { BIT6,  6,  6, 303 }, { BIT5,  4,  4, 304 },
{ BIT4,  2,  2, 305 }, { BIT3,  6,  6, 306 }, { BIT1,  4,  4, 307 }, { BIT0,  6,  5, 308 }, { BIT7,  8,  8, 309 }, { BIT5,  4,  4, 310 }, { BIT4,  2,  2, 311 }, { BIT3,  4,  4, 312 },
{ BIT2,  2,  2, 313 }, { BIT1,  4,  4, 314 }, { BIT0,  8,  7, 315 }, { BIT6,  6,  6, 316 }, { BIT5,  4,  4, 317 }, { BIT4,  6,  6, 318 }, { BIT2,  2,  2, 319 }, { BIT1,  4,  4, 320 },
{ BIT0,  6,  5, 321 }, { BIT7,  2,  2, 322 }, { BIT6,  6,  6, 323 }, { BIT5,  6,  6, 324 }, { BIT3,  4,  4, 325 }, { BIT2,  2,  2, 326 }, { BIT1,  4,  4, 327 }, { BIT0,  6,  5, 328 },
{ BIT7,  2,  2, 329 }, { BIT6,  6,  6, 330 }, { BIT5,  4,  4, 331 }, { BIT4,  2,  2, 332 }, { BIT3,  4,  4, 333 }, { BIT2,  2,  2, 334 }, { BIT1, 10,  9, 335 }, { BIT7,  2,  2, 288 },
{ BIT7, 10,  1, 337 }, { BIT1,  2,  0, 338 }, { BIT2,  4,  0, 339 }, { BIT3,  2,  0, 340 }, { BIT4,  4,  0, 341 }, { BIT5,  6,  0, 342 }, { BIT6,  2,  0, 343 }, { BIT7,  6,  1, 344 },
{ BIT0,  4,  0, 345 }, { BIT1,  2,  0, 346 }, { BIT2,  4,  0, 347 }, { BIT3,  6,  0, 348 }, { BIT5,  6,  0, 349 }, { BIT6,  2,  0, 350 }, { BIT7,  6,  1, 351 }, { BIT0,  4,  0, 352 },
{ BIT1,  2,  0, 353 }, { BIT2,  6,  0, 354 }, { BIT4,  4,  0, 355 }, { BIT5,  6,  0, 356 }, { BIT6,  8,  1, 357 }, { BIT0,  4,  0, 358 }, { BIT1,  2,  0, 359 }, { BIT2,  4,  0, 360 },
{ BIT3,  2,  0, 361 }, { BIT4,  4,  0, 362 }, { BIT5,  8,  0, 363 }, { BIT7,  6,  1, 364 }, { BIT0,  4,  0, 365 }, { BIT1,  6,  0, 366 }, { BIT3,  2,  0, 367 }, { BIT4,  4,  0, 368 },
{ BIT5,  6,  0, 369 }, { BIT6,  2,  0, 370 }, { BIT7,  6,  1, 371 }, { BIT0,  6,  0, 372 }, { BIT2,  4,  0, 373 }, { BIT3,  2,  0, 374 }, { BIT4,  4,  0, 375 }, { BIT5,  6,  0, 376 },
{ BIT6,  2,  0, 377 }, { BIT7,  6,  1, 378 }, { BIT0,  4,  0, 379 }, { BIT1,  2,  0, 380 }, { BIT2,  4,  0, 381 }, { BIT3,  2,  0, 382 }, { BIT4, 10,  0, 383 }, { BIT6,  2,  0, 336 }
}};
} 
namespace primesieve {
void EratBig::init(uint64_t stop,
uint64_t maxPrime,
const Vector<uint64_t>& sieve,
MemoryPool& memoryPool)
{
uint64_t sieveBytes = sieve.size() * sizeof(uint64_t);
ASSERT(isPow2(sieveBytes));
ASSERT(sieveBytes <= SievingPrime::MAX_MULTIPLEINDEX + 1);
stop_ = stop;
maxPrime_ = maxPrime;
log2SieveBytes_ = ilog2(sieveBytes);
moduloSieveBytes_ = sieveBytes - 1;
memoryPool_ = &memoryPool;
uint64_t maxSievingPrime = maxPrime_ / 30;
uint64_t maxNextMultiple = maxSievingPrime * getMaxFactor() + getMaxFactor();
uint64_t maxMultipleIndex = sieveBytes - 1 + maxNextMultiple;
uint64_t maxSegmentIndex = maxMultipleIndex >> log2SieveBytes_;
uint64_t maxSize = maxSegmentIndex + 1;
buckets_.reserve(maxSize);
}
void EratBig::storeSievingPrime(uint64_t prime,
uint64_t multipleIndex,
uint64_t wheelIndex)
{
uint64_t sieveBytes = 1ull << log2SieveBytes_;
uint64_t sievingPrime = prime / 30;
uint64_t maxNextMultiple = sievingPrime * getMaxFactor() + getMaxFactor();
uint64_t maxMultipleIndex = sieveBytes - 1 + maxNextMultiple;
uint64_t maxSegmentIndex = maxMultipleIndex >> log2SieveBytes_;
uint64_t newSize = maxSegmentIndex + 1;
uint64_t segment = multipleIndex >> log2SieveBytes_;
multipleIndex &= moduloSieveBytes_;
while (buckets_.size() < newSize)
buckets_.push_back(nullptr);
ASSERT(prime <= maxPrime_);
ASSERT(segment < buckets_.size());
if (Bucket::isFull(buckets_[segment]))
memoryPool_->addBucket(buckets_[segment]);
buckets_[segment]++->set(sievingPrime, multipleIndex, wheelIndex);
}
void EratBig::crossOff(Vector<uint64_t>& sieve)
{
uint8_t* sieve8 = (uint8_t*) sieve.data();
while (buckets_[0])
{
Bucket* bucket = Bucket::get(buckets_[0]);
bucket->setEnd(buckets_[0]);
buckets_[0] = nullptr;
while (bucket)
{
crossOff(sieve8, bucket->begin(), bucket->end());
Bucket* processed = bucket;
bucket = bucket->next();
memoryPool_->freeBucket(processed);
}
}
auto* bucket = buckets_[0];
std::copy(buckets_.begin() + 1, buckets_.end(), buckets_.begin());
buckets_.back() = bucket;
if (remainingBytes_ != uint64_t(-1))
{
const uint64_t bytes = uint64_t(1) << log2SieveBytes_;
remainingBytes_ = remainingBytes_ > bytes ? remainingBytes_ - bytes : 0;
}
}
void EratBig::crossOff(uint8_t* sieve,
SievingPrime* prime,
SievingPrime* end)
{
auto buckets = buckets_.data();
MemoryPool& memoryPool = *memoryPool_;
std::size_t moduloSieveBytes = moduloSieveBytes_;
std::size_t log2SieveBytes = log2SieveBytes_;
for (; prime != end; prime++)
{
std::size_t multipleIndex = prime->getMultipleIndex();
std::size_t wheelIndex    = prime->getWheelIndex();
std::size_t sievingPrime  = prime->getSievingPrime();
sieve[multipleIndex] &= wheel210[wheelIndex].unsetBit;
multipleIndex += wheel210[wheelIndex].nextMultipleFactor * sievingPrime;
multipleIndex += wheel210[wheelIndex].correct;
wheelIndex = wheel210[wheelIndex].next;
// This hit has been crossed. Discard the state when its next hit lies
// beyond the complete finite target, instead of allocating a future bucket.
if (multipleIndex >= remainingBytes_) continue;
std::size_t segment = multipleIndex >> log2SieveBytes;
multipleIndex &= moduloSieveBytes;
if (Bucket::isFull(buckets[segment]))
memoryPool.addBucket(buckets[segment]);
buckets[segment]++->set(sievingPrime, multipleIndex, wheelIndex);
}
}
} 

#undef CHECK_FINISHED

#ifndef PRESIEVE_HPP
#define PRESIEVE_HPP
#include <stdint.h>
namespace primesieve {
class PreSieve
{
public:
static void preSieve(Vector<uint64_t>& sieve, unsigned __int128 segmentLow);
static uint64_t getMaxPrime() { return 199; }
};
} 
#endif
namespace {
const primesieve::Array<size_t,20> preSieveTableSizes={5957,6479,6409,6683,6751,7097,7897,8201,8357,8777,9017,8249,8611,8881,9167,9797,28891,32399,36863,39203};
static constexpr unsigned root_ps[20][3]={{7,23,37},{11,19,31},{13,17,29},{41,163},{43,157},{47,151},{53,149},{59,139},{61,137},{67,131},{71,127},{73,113},{79,109},{83,107},{89,103},{97,101},{167,173,0},{179,181,0},{191,193,0},{197,199,0}};
static constexpr size_t root_sizes[20]={5957,6479,6409,6683,6751,7097,7897,8201,8357,8777,9017,8249,8611,8881,9167,9797,28891,32399,36863,39203};
template<unsigned T>struct RootPreTable{uint8_t a[root_sizes[T]]{};constexpr RootPreTable(){for(auto&x:a)x=255;const unsigned off[8]={7,11,13,17,19,23,29,31};for(unsigned p:root_ps[T])if(p){unsigned inv=1;while((30*inv)%p!=1)++inv;for(unsigned b=0;b<8;b++){unsigned start=((p-off[b]%p)*inv)%p;for(size_t j=start;j<root_sizes[T];j+=p)a[j]&=~(1u<<b);}}}};
static constexpr RootPreTable<0> root_pre_0{};
static constexpr RootPreTable<1> root_pre_1{};
static constexpr RootPreTable<2> root_pre_2{};
static constexpr RootPreTable<3> root_pre_3{};
static constexpr RootPreTable<4> root_pre_4{};
static constexpr RootPreTable<5> root_pre_5{};
static constexpr RootPreTable<6> root_pre_6{};
static constexpr RootPreTable<7> root_pre_7{};
static constexpr RootPreTable<8> root_pre_8{};
static constexpr RootPreTable<9> root_pre_9{};
static constexpr RootPreTable<10> root_pre_10{};
static constexpr RootPreTable<11> root_pre_11{};
static constexpr RootPreTable<12> root_pre_12{};
static constexpr RootPreTable<13> root_pre_13{};
static constexpr RootPreTable<14> root_pre_14{};
static constexpr RootPreTable<15> root_pre_15{};
static constexpr RootPreTable<16> root_pre_16{};
static constexpr RootPreTable<17> root_pre_17{};
static constexpr RootPreTable<18> root_pre_18{};
static constexpr RootPreTable<19> root_pre_19{};
const primesieve::Array<const uint8_t*,20> preSieveTables={root_pre_0.a,root_pre_1.a,root_pre_2.a,root_pre_3.a,root_pre_4.a,root_pre_5.a,root_pre_6.a,root_pre_7.a,root_pre_8.a,root_pre_9.a,root_pre_10.a,root_pre_11.a,root_pre_12.a,root_pre_13.a,root_pre_14.a,root_pre_15.a,root_pre_16.a,root_pre_17.a,root_pre_18.a,root_pre_19.a};

}
#ifndef CPU_ARCH_MACROS_HPP
#define CPU_ARCH_MACROS_HPP
#if defined(ENABLE_MULTIARCH_AVX2)
#define ENABLE_MULTIARCH_AVX2_BMI2
#endif
#if defined(__AVX512F__) && \
defined(__AVX512VBMI__) && \
defined(__AVX512VBMI2__) && \
defined(__POPCNT__) && \
!defined(__i386__) && \
__has_include(<immintrin.h>)
#define ENABLE_AVX512_VBMI2
#undef ENABLE_MULTIARCH_AVX512_VBMI2
#undef ENABLE_MULTIARCH_AVX2_BMI2
#elif defined(__AVX2__) && \
defined(__BMI2__) && \
defined(__POPCNT__) && \
!defined(__i386__) && \
__has_include(<immintrin.h>)
#define ENABLE_AVX2_BMI2
#undef ENABLE_MULTIARCH_AVX2_BMI2
#elif defined(__AVX2__) && \
defined(_MSC_VER) && \
!defined(_M_IX86) && \
__has_include(<immintrin.h>)
#define ENABLE_AVX2_BMI2
#undef ENABLE_MULTIARCH_AVX2_BMI2
#endif
#if defined(__AVX512F__) && \
defined(__AVX512BW__) && \
__has_include(<immintrin.h>)
#define ENABLE_AVX512_BW
#undef ENABLE_MULTIARCH_AVX512_BW
#undef ENABLE_MULTIARCH_AVX2
#elif defined(__AVX2__) && \
__has_include(<immintrin.h>)
#define ENABLE_AVX2
#undef ENABLE_MULTIARCH_AVX2
#elif (defined(__SSE2__) || \
defined(_M_X64)) && \
__has_include(<emmintrin.h>)
#define ENABLE_SSE2
#elif defined(__ARM_FEATURE_SVE) && \
__has_include(<arm_sve.h>)
#define ENABLE_ARM_SVE
#undef ENABLE_MULTIARCH_ARM_SVE
#endif
#if (defined(__aarch64__) || \
defined(_M_ARM64)) && \
__has_include(<arm_neon.h>)
#define ENABLE_ARM_NEON
#endif
#endif
#include <stdint.h>
#include <algorithm>
#include <cstddef>
#include <utility>
#define PRESIEVE1_DEFAULT presieve1_x86_avx2
#define PRESIEVE2_DEFAULT presieve2_x86_avx2
#ifndef PRESIEVE_X86_AVX2_HPP
#define PRESIEVE_X86_AVX2_HPP
#include <immintrin.h>
#include <x86intrin.h>
#include <stdint.h>
#include <cstddef>
namespace {
#if defined(ENABLE_MULTIARCH_AVX2)
PRIMESIEVE_TARGET_ATTRIBUTE("avx2")
#endif
void presieve1_x86_avx2(const uint8_t* __restrict preSieved0,
const uint8_t* __restrict preSieved1,
const uint8_t* __restrict preSieved2,
const uint8_t* __restrict preSieved3,
uint8_t* __restrict sieve,
std::size_t bytes)
{
std::size_t i = 0;
std::size_t limit = bytes - bytes % sizeof(__m256i);
NO_UNROLL_LOOP
for (; i < limit; i += sizeof(__m256i))
{
_mm256_storeu_si256((__m256i*) &sieve[i],
_mm256_and_si256(
_mm256_and_si256(_mm256_loadu_si256((const __m256i*) &preSieved0[i]), _mm256_loadu_si256((const __m256i*) &preSieved1[i])),
_mm256_and_si256(_mm256_loadu_si256((const __m256i*) &preSieved2[i]), _mm256_loadu_si256((const __m256i*) &preSieved3[i]))));
}
NO_UNROLL_LOOP
NO_VECTORIZE_LOOP
for (; i < bytes; i++)
sieve[i] = preSieved0[i] & preSieved1[i] & preSieved2[i] & preSieved3[i];
}
#if defined(ENABLE_MULTIARCH_AVX2)
PRIMESIEVE_TARGET_ATTRIBUTE("avx2")
#endif
void presieve2_x86_avx2(const uint8_t* __restrict preSieved0,
const uint8_t* __restrict preSieved1,
const uint8_t* __restrict preSieved2,
const uint8_t* __restrict preSieved3,
uint8_t* __restrict sieve,
std::size_t bytes)
{
std::size_t i = 0;
std::size_t limit = bytes - bytes % sizeof(__m256i);
NO_UNROLL_LOOP
for (; i < limit; i += sizeof(__m256i))
{
_mm256_storeu_si256((__m256i*) &sieve[i],
_mm256_and_si256(_mm256_loadu_si256((const __m256i*) &sieve[i]), _mm256_and_si256(
_mm256_and_si256(_mm256_loadu_si256((const __m256i*) &preSieved0[i]), _mm256_loadu_si256((const __m256i*) &preSieved1[i])),
_mm256_and_si256(_mm256_loadu_si256((const __m256i*) &preSieved2[i]), _mm256_loadu_si256((const __m256i*) &preSieved3[i])))));
}
NO_UNROLL_LOOP
NO_VECTORIZE_LOOP
for (; i < bytes; i++)
sieve[i] &= preSieved0[i] & preSieved1[i] & preSieved2[i] & preSieved3[i];
}
} 
#endif
namespace {
template <typename... Args>
void presieve1(Args&&... args)
{
#if defined(ENABLE_MULTIARCH_AVX512_BW)
if (cpu_supports_avx512_bw)
return presieve1_x86_avx512(std::forward<Args>(args)...);
#endif
#if defined(ENABLE_MULTIARCH_AVX2)
if (cpu_supports_avx2)
return presieve1_x86_avx2(std::forward<Args>(args)...);
#endif
#if defined(ENABLE_MULTIARCH_ARM_SVE)
if (cpu_supports_sve)
return presieve1_arm_sve(std::forward<Args>(args)...);
#endif
PRESIEVE1_DEFAULT(std::forward<Args>(args)...);
}
template <typename... Args>
void presieve2(Args&&... args)
{
#if defined(ENABLE_MULTIARCH_AVX512_BW)
if (cpu_supports_avx512_bw)
return presieve2_x86_avx512(std::forward<Args>(args)...);
#endif
#if defined(ENABLE_MULTIARCH_AVX2)
if (cpu_supports_avx2)
return presieve2_x86_avx2(std::forward<Args>(args)...);
#endif
#if defined(ENABLE_MULTIARCH_ARM_SVE)
if (cpu_supports_sve)
return presieve2_arm_sve(std::forward<Args>(args)...);
#endif
PRESIEVE2_DEFAULT(std::forward<Args>(args)...);
}
} 
namespace primesieve {
void PreSieve::preSieve(Vector<uint64_t>& sieve, unsigned __int128 segmentLow)
{
uint64_t offset = 0;
uint64_t pos0, pos1, pos2, pos3;
uint8_t* sieve8 = (uint8_t*) sieve.data();
uint64_t sieveBytes = sieve.size() * sizeof(uint64_t);
pos0 = (segmentLow % (preSieveTableSizes[0] * 30)) / 30;
pos1 = (segmentLow % (preSieveTableSizes[1] * 30)) / 30;
pos2 = (segmentLow % (preSieveTableSizes[2] * 30)) / 30;
pos3 = (segmentLow % (preSieveTableSizes[3] * 30)) / 30;
while (offset < sieveBytes)
{
uint64_t bytesToCopy = sieveBytes - offset;
bytesToCopy = std::min(bytesToCopy, uint64_t(preSieveTableSizes[0] - pos0));
bytesToCopy = std::min(bytesToCopy, uint64_t(preSieveTableSizes[1] - pos1));
bytesToCopy = std::min(bytesToCopy, uint64_t(preSieveTableSizes[2] - pos2));
bytesToCopy = std::min(bytesToCopy, uint64_t(preSieveTableSizes[3] - pos3));
ASSERT(bytesToCopy > 0);
presieve1(preSieveTables[0] + pos0,
preSieveTables[1] + pos1,
preSieveTables[2] + pos2,
preSieveTables[3] + pos3,
&sieve8[offset], bytesToCopy);
pos0 += bytesToCopy;
pos1 += bytesToCopy;
pos2 += bytesToCopy;
pos3 += bytesToCopy;
offset += bytesToCopy;
pos0 *= (pos0 < preSieveTableSizes[0]);
pos1 *= (pos1 < preSieveTableSizes[1]);
pos2 *= (pos2 < preSieveTableSizes[2]);
pos3 *= (pos3 < preSieveTableSizes[3]);
}
for (std::size_t i = 4; i < preSieveTables.size(); i += 4)
{
offset = 0;
pos0 = (segmentLow % (preSieveTableSizes[i+0] * 30)) / 30;
pos1 = (segmentLow % (preSieveTableSizes[i+1] * 30)) / 30;
pos2 = (segmentLow % (preSieveTableSizes[i+2] * 30)) / 30;
pos3 = (segmentLow % (preSieveTableSizes[i+3] * 30)) / 30;
while (offset < sieveBytes)
{
uint64_t bytesToCopy = sieveBytes - offset;
bytesToCopy = std::min(bytesToCopy, uint64_t(preSieveTableSizes[i+0] - pos0));
bytesToCopy = std::min(bytesToCopy, uint64_t(preSieveTableSizes[i+1] - pos1));
bytesToCopy = std::min(bytesToCopy, uint64_t(preSieveTableSizes[i+2] - pos2));
bytesToCopy = std::min(bytesToCopy, uint64_t(preSieveTableSizes[i+3] - pos3));
ASSERT(bytesToCopy > 0);
presieve2(preSieveTables[i+0] + pos0,
preSieveTables[i+1] + pos1,
preSieveTables[i+2] + pos2,
preSieveTables[i+3] + pos3,
&sieve8[offset], bytesToCopy);
pos0 += bytesToCopy;
pos1 += bytesToCopy;
pos2 += bytesToCopy;
pos3 += bytesToCopy;
offset += bytesToCopy;
pos0 *= (pos0 < preSieveTableSizes[i+0]);
pos1 *= (pos1 < preSieveTableSizes[i+1]);
pos2 *= (pos2 < preSieveTableSizes[i+2]);
pos3 *= (pos3 < preSieveTableSizes[i+3]);
}
}
if (segmentLow <= getMaxPrime())
{
uint64_t i = segmentLow / 30;
Array<uint8_t, 8> primeBits = { 0xff, 0xef, 0x77, 0x3f, 0xdb, 0xed, 0x9e, 0xfc };
ASSERT(sieveBytes >= primeBits.size());
for (std::size_t j = 0; i + j < primeBits.size(); j++)
sieve8[j] = primeBits[i + j];
}
}
} 

#undef CHECK_FINISHED

#ifndef ERAT_HPP
#define ERAT_HPP
#ifndef CTZ_HPP
#define CTZ_HPP
#include <stdint.h>
#if defined(__x86_64__) || \
defined(_M_X64)
#define IS_X64
#endif
#if defined(__BMI__) || \
(defined(_MSC_VER) && defined(__AVX2__))
#define HAS_TZCNT
#endif
#if (defined(__GNUC__) || \
defined(__clang__)) && \
defined(__x86_64__)
#define HAS_CTZ64
#define CTZ64_SUPPORTS_ZERO
namespace primesieve {
ALWAYS_INLINE uint64_t ctz64(uint64_t x)
{
#if defined(HAS_TZCNT)
__asm__("tzcnt %1, %0" : "=r"(x) : "r"(x));
return x;
#else
__asm__("rep bsf %1, %0" : "=r"(x) : "0"(x));
ASSERT(x <= 64);
return x;
#endif
}
} 
#elif (defined(__GNUC__) || \
defined(__clang__)) && \
defined(__aarch64__)
#define HAS_CTZ64
#define CTZ64_SUPPORTS_ZERO
namespace primesieve {
ALWAYS_INLINE uint64_t ctz64(uint64_t x)
{
__asm__("rbit %0, %1 \n\t"
"clz %0, %0  \n\t"
: "=r" (x)
: "r" (x));
return x;
}
} 
#elif defined(_MSC_VER) && \
defined(HAS_TZCNT) && \
__has_include(<immintrin.h>)
#include <immintrin.h>
#include <x86intrin.h>
#define HAS_CTZ64
#define CTZ64_SUPPORTS_ZERO
#define ctz64(x) _tzcnt_u64(x)
#elif __cplusplus >= 202002L && \
__has_include(<bit>) && \
(!defined(IS_X64) || defined(HAS_TZCNT))
#include <bit>
#define CTZ64_SUPPORTS_ZERO
#define HAS_CTZ64
namespace primesieve {
ALWAYS_INLINE int ctz64(uint64_t x)
{
return std::countr_zero(x);
}
} 
#elif defined(__GNUC__) || \
__has_builtin(__builtin_ctzl)
#define HAS_CTZ64
namespace primesieve {
ALWAYS_INLINE int ctz64(uint64_t x)
{
ASSERT(x != 0);
#if __cplusplus >= 201703L
if constexpr(sizeof(int) >= sizeof(uint64_t))
return __builtin_ctz(x);
else if constexpr(sizeof(long) >= sizeof(uint64_t))
return __builtin_ctzl(x);
else if constexpr(sizeof(long long) >= sizeof(uint64_t))
return __builtin_ctzll(x);
#else
return __builtin_ctzll(x);
#endif
}
} 
#elif defined(_MSC_VER) && \
defined(_WIN64) && \
__has_include(<intrin.h>)
#include <intrin.h>
#define HAS_CTZ64
namespace primesieve {
ALWAYS_INLINE int ctz64(uint64_t x)
{
ASSERT(x != 0);
unsigned long r;
_BitScanForward64(&r, x);
return (int) r;
}
} 
#endif
#endif 
#include <stdint.h>
namespace primesieve {
class MemoryPool;
class Erat
{
public:
uint64_t getStop() const;
protected:
uint64_t start_ = 0;
uint64_t stop_ = 0;
uint64_t segmentLow_ = ~0ull;
uint64_t segmentHigh_ = 0;
Vector<uint64_t> sieve_;
Erat() = default;
Erat(uint64_t, uint64_t);
void init(uint64_t, uint64_t, uint64_t, MemoryPool& memoryPool);
void addSievingPrime(uint64_t);
NOINLINE void sieveSegment();
bool hasNextSegment() const;
static uint64_t nextPrime(uint64_t, uint64_t);
private:
uint64_t maxEratSmall_ = 0;
uint64_t maxEratMedium_ = 0;
EratSmall eratSmall_;
EratBig eratBig_;
EratMedium eratMedium_;
static uint64_t byteRemainder(uint64_t);
static uint64_t getL1CacheSize();
void initAlgorithms(uint64_t maxSieveBytes, MemoryPool&);
void preSieve();
void crossOff();
void sieveLastSegment();
};
ALWAYS_INLINE uint64_t Erat::nextPrime(uint64_t bits, uint64_t low)
{
#if defined(CTZ64_SUPPORTS_ZERO)
auto bitIndex = ctz64(bits);
uint64_t bitValue = bitValues[bitIndex];
#elif defined(HAS_CTZ64)
auto bitIndex = ctz64(bits | (1ull << 63));
uint64_t bitValue = bitValues[bitIndex];
#else
uint64_t debruijn = 0x3F08A4C6ACB9DBD;
uint64_t hash = ((bits ^ (bits - 1)) * debruijn) >> 58;
uint64_t bitValue = bruijnBitValues[hash];
#endif
uint64_t prime = low + bitValue;
return prime;
}
ALWAYS_INLINE void Erat::addSievingPrime(uint64_t prime)
{
if (prime > maxEratMedium_)   eratBig_.addSievingPrime(prime, segmentLow_);
else if (prime > maxEratSmall_) eratMedium_.addSievingPrime(prime, segmentLow_);
else  eratSmall_.addSievingPrime(prime, segmentLow_);
}
ALWAYS_INLINE uint64_t Erat::getStop() const
{
return stop_;
}
} 
#endif
#include <stdint.h>
#include <algorithm>
#include <limits>
namespace {
const primesieve::Array<uint8_t, 37> unsetSmaller =
{
0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
0xfe, 0xfe, 0xfe, 0xfe, 0xfc, 0xfc, 0xf8, 0xf8,
0xf8, 0xf8, 0xf0, 0xf0, 0xe0, 0xe0, 0xe0, 0xe0,
0xc0, 0xc0, 0xc0, 0xc0, 0xc0, 0xc0, 0x80, 0x80,
0x00, 0x00, 0x00, 0x00, 0x00
};
const primesieve::Array<uint8_t, 37> unsetLarger =
{
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x01,
0x01, 0x01, 0x01, 0x03, 0x03, 0x07, 0x07, 0x07,
0x07, 0x0f, 0x0f, 0x1f, 0x1f, 0x1f, 0x1f, 0x3f,
0x3f, 0x3f, 0x3f, 0x3f, 0x3f, 0x7f, 0x7f, 0xff,
0xff, 0xff, 0xff, 0xff, 0xff
};
} 
namespace primesieve {
Erat::Erat(uint64_t start, uint64_t stop) :
start_(start),
stop_(stop)
{ }
void Erat::init(uint64_t start,
uint64_t stop,
uint64_t maxSieveSize,
MemoryPool& memoryPool)
{
if_unlikely(start > stop || 
start >= std::numeric_limits<uint64_t>::max())
return;
ASSERT(start >= 7);
ASSERT(maxSieveSize >= 16);
ASSERT(maxSieveSize <= 8192);
start_ = start;
stop_ = stop;
uint64_t maxSieveBytes = maxSieveSize << 10;
initAlgorithms(maxSieveBytes, memoryPool);
}
uint64_t Erat::getL1CacheSize(){return 32768;}
void Erat::initAlgorithms(uint64_t maxSieveBytes,
MemoryPool& memoryPool)
{
uint64_t sqrtStop = isqrt(stop_);
uint64_t l1CacheSize = getL1CacheSize();
l1CacheSize = inBetween(16 << 10, l1CacheSize, 8192 << 10);
l1CacheSize = ceilDiv(l1CacheSize, sizeof(uint64_t)) * sizeof(uint64_t);
maxSieveBytes = ceilDiv(maxSieveBytes, sizeof(uint64_t)) * sizeof(uint64_t);
uint64_t minSieveBytes = std::min(l1CacheSize, maxSieveBytes);
uint64_t sieveBytes = uint64_t(sqrtStop * config::FACTOR_SIEVESIZE);
if (sieveBytes > minSieveBytes)
sieveBytes -= sieveBytes % minSieveBytes;
sieveBytes = inBetween(minSieveBytes, sieveBytes, maxSieveBytes);
sieveBytes = inBetween(16 << 10, sieveBytes, 8192 << 10);
minSieveBytes = std::min(l1CacheSize, sieveBytes);
maxEratSmall_ = (uint64_t) (minSieveBytes * config::FACTOR_ERATSMALL);
maxEratMedium_ = (uint64_t) (sieveBytes * config::FACTOR_ERATMEDIUM);
if (sqrtStop > maxEratMedium_)
{
sieveBytes = floorPow2(sieveBytes);
minSieveBytes = std::min(l1CacheSize, sieveBytes);
maxEratSmall_ = (uint64_t) (minSieveBytes * config::FACTOR_ERATSMALL);
maxEratMedium_ = (uint64_t) (sieveBytes * config::FACTOR_ERATMEDIUM);
}
maxEratSmall_ = std::min(maxEratSmall_, sqrtStop);
maxEratMedium_ = std::min(maxEratMedium_, sqrtStop);
uint64_t rem = byteRemainder(start_);
uint64_t dist = sieveBytes * 30 + 6;
segmentLow_ = start_ - rem;
segmentHigh_ = checkedAdd(segmentLow_, dist);
segmentHigh_ = std::min(segmentHigh_, stop_);
if (segmentHigh_ >= stop_ &&
sqrtStop <= maxEratMedium_)
{
uint64_t rem = byteRemainder(stop_);
uint64_t dist = (stop_ - rem) - segmentLow_;
sieveBytes = dist / 30 + 1;
sieveBytes = ceilDiv(sieveBytes, sizeof(uint64_t)) * sizeof(uint64_t);
}
ASSERT(sieveBytes % sizeof(uint64_t) == 0);
sieve_.resize(sieveBytes / sizeof(uint64_t));
if (sqrtStop > PreSieve::getMaxPrime())
eratSmall_.init(stop_, l1CacheSize, maxEratSmall_);
if (sqrtStop > maxEratSmall_)
eratMedium_.init(stop_, maxEratMedium_, memoryPool);
if (sqrtStop > maxEratMedium_)
eratBig_.init(stop_, sqrtStop, sieve_, memoryPool);
}
bool Erat::hasNextSegment() const
{
return segmentLow_ < stop_;
}
uint64_t Erat::byteRemainder(uint64_t n)
{
ASSERT(n >= 7);
return (n - 7) % 30 + 7;
}
void Erat::sieveSegment()
{
if (segmentHigh_ < stop_)
{
preSieve();
crossOff();
uint64_t dist = sieve_.size() * 240;
segmentLow_ = checkedAdd(segmentLow_, dist);
segmentHigh_ = checkedAdd(segmentHigh_, dist);
segmentHigh_ = std::min(segmentHigh_, stop_);
}
else
sieveLastSegment();
}
void Erat::sieveLastSegment()
{
uint64_t rem = byteRemainder(stop_);
uint64_t dist = (stop_ - rem) - segmentLow_;
uint64_t sieveBytes = dist / 30 + 1;
sieve_.resize(ceilDiv(sieveBytes, sizeof(uint64_t)));
preSieve();
crossOff();
uint8_t* sieve = (uint8_t*) sieve_.data();
sieve[sieveBytes - 1] &= unsetLarger[rem];
uint64_t i = sieveBytes;
for (; i % sizeof(uint64_t); i++)
sieve[i] = 0;
segmentLow_ = stop_;
}
void Erat::preSieve()
{
PreSieve::preSieve(sieve_, segmentLow_);
if (segmentLow_ <= start_)
{
uint64_t rem = byteRemainder(start_);
uint8_t* sieve = (uint8_t*) sieve_.data();
sieve[0] &= unsetSmaller[rem];
}
}
void Erat::crossOff()
{
if (eratSmall_.hasSievingPrimes())
eratSmall_.crossOff(sieve_);
if (eratMedium_.hasSievingPrimes())
eratMedium_.crossOff(sieve_);
if (eratBig_.hasSievingPrimes())
eratBig_.crossOff(sieve_);
}
} 



struct RootBasePrimes{uint32_t p[9592]{};constexpr RootBasePrimes(){bool composite[100001]={};unsigned count=0;for(unsigned i=2;i<=100000;i++)if(!composite[i]){p[count++]=i;if(uint64_t(i)*i<=100000)for(unsigned j=i*i;j<=100000;j+=i)composite[j]=true;}}};
static constexpr RootBasePrimes root_base_primes{};
namespace base_stream {
class Generator : public primesieve::Erat {
primesieve::MemoryPool pool;
public:
template<class F> void segments(uint64_t n,F fn) {
init(7,n-1,128,pool);
size_t active=46;
while(hasNextSegment()){while(active<9592&&uint64_t(root_base_primes.p[active])*root_base_primes.p[active]<=segmentHigh_)addSievingPrime(root_base_primes.p[active++]);uint64_t low=segmentLow_;sieveSegment();fn(low,(const unsigned char*)sieve_.data(),sieve_.size()*8);}
}
};
}


static inline __m256i gload32(const void*p){__m256i r;__asm__("vmovdqu %1,%0":"=v"(r):"m"(*(const __m256i*)p));return r;}
namespace root_sieve_expand {
struct Lookup{uint32_t a[256]{};constexpr Lookup(){const unsigned off[8]={7,11,13,17,19,23,29,31};for(unsigned v=0;v<256;v++)for(unsigned k=0;k<8;k++)if(v>>k&1)a[v]|=1u<<off[k];}};
static constexpr Lookup table{};
}
void sieve(uint64_t input_n,char*dest){constexpr uint64_t n=UINT64_C(10000000000);if(input_n!=n)__builtin_trap();
 auto*out=(unsigned char*)dest;const size_t total=(n+7)/8;
 if(n<8){if(n)*out=(unsigned char)(0xacu&((1u<<n)-1));return;}
 uint64_t carry=0;__m256i root_pv=_mm256_setzero_si256();
 constexpr uint64_t mask=[](){uint64_t m=0;for(unsigned x:{7,11,13,17,19,23,29,31})m|=(1ull<<x)|(1ull<<(x+30));return m;}();
const __m256i root_c1=_mm256_set1_epi8(1),root_c2=_mm256_set1_epi8(2),root_c4=_mm256_set1_epi8(4),root_c8=_mm256_set1_epi8(8),root_c16=_mm256_set1_epi8(16),root_c32=_mm256_set1_epi8(32),root_c64=_mm256_set1_epi8(64),root_c128=_mm256_set1_epi8(-128),root_ncarry=_mm256_set1_epi32(2),root_nshift=_mm256_setr_epi32(0,2,4,6,0,2,4,6);
base_stream::Generator generator;
 generator.segments(n,[&](uint64_t low,const unsigned char*src,size_t bytes){
 size_t pos=low>>3;
 size_t j=0;
 alignas(64) unsigned char block[1024];
 if(!(uintptr_t(out+pos)&31)){
  alignas(64) unsigned char block[2][1024];size_t pend=0,ppos=0;int bb=0;
  for(;j+256<=bytes&&pos+960<=total;j+=256,pos+=960){
#pragma GCC unroll 2
for(unsigned k=0;k<8;k++){
const auto root_nv=gload32(src+j+32*k);

const auto root_prev=_mm256_alignr_epi8(root_nv,_mm256_permute2x128_si256(root_nv,root_pv,0x03),15);
const auto root_nc=_mm256_and_si256(_mm256_srli_epi16(root_prev,6),root_ncarry);
const auto root_b0=_mm256_or_si256(_mm256_slli_epi16(_mm256_and_si256(root_nv,root_c1),7),root_nc);
const auto root_b1=_mm256_or_si256(_mm256_slli_epi16(_mm256_and_si256(root_nv,root_c2),2),_mm256_slli_epi16(_mm256_and_si256(root_nv,root_c4),3));
const auto root_b2=_mm256_or_si256(_mm256_srli_epi16(_mm256_and_si256(root_nv,root_c8),2),_mm256_or_si256(_mm256_srli_epi16(_mm256_and_si256(root_nv,root_c16),1),_mm256_slli_epi16(_mm256_and_si256(root_nv,root_c32),2)));
const auto root_b3=_mm256_or_si256(_mm256_srli_epi16(_mm256_and_si256(root_nv,root_c64),1),_mm256_and_si256(root_nv,root_c128));
const auto root_l0=_mm256_unpacklo_epi8(root_b0,root_b1),root_l1=_mm256_unpackhi_epi8(root_b0,root_b1);
const auto root_h0=_mm256_unpacklo_epi8(root_b2,root_b3),root_h1=_mm256_unpackhi_epi8(root_b2,root_b3);
const auto root_o0=_mm256_srlv_epi32(_mm256_unpacklo_epi16(root_l0,root_h0),root_nshift);
const auto root_o1=_mm256_srlv_epi32(_mm256_unpackhi_epi16(root_l0,root_h0),root_nshift);
const auto root_o2=_mm256_srlv_epi32(_mm256_unpacklo_epi16(root_l1,root_h1),root_nshift);
const auto root_o3=_mm256_srlv_epi32(_mm256_unpackhi_epi16(root_l1,root_h1),root_nshift);
_mm_storeu_si128((__m128i*)(block[bb]+120*k+0),_mm256_castsi256_si128(root_o0));
_mm_storeu_si128((__m128i*)(block[bb]+120*k+15),_mm256_castsi256_si128(root_o1));
_mm_storeu_si128((__m128i*)(block[bb]+120*k+30),_mm256_castsi256_si128(root_o2));
_mm_storeu_si128((__m128i*)(block[bb]+120*k+45),_mm256_castsi256_si128(root_o3));
_mm_storeu_si128((__m128i*)(block[bb]+120*k+60),_mm256_extracti128_si256(root_o0,1));
_mm_storeu_si128((__m128i*)(block[bb]+120*k+75),_mm256_extracti128_si256(root_o1,1));
_mm_storeu_si128((__m128i*)(block[bb]+120*k+90),_mm256_extracti128_si256(root_o2,1));
_mm_storeu_si128((__m128i*)(block[bb]+120*k+105),_mm256_extracti128_si256(root_o3,1));
carry=(unsigned(_mm256_movemask_epi8(root_nv))>>30)&2u;
root_pv=root_nv;if(pend)for(unsigned t=0;t<4;t++){unsigned mm=4*k+t;if(mm<30)_mm256_stream_si256((__m256i*)(out+ppos+32*mm),_mm256_load_si256((const __m256i*)(block[bb^1]+32*mm)));}
}
   ppos=pos;pend=1;bb^=1;
  }
  if(pend)for(unsigned t=0;t<30;t++)_mm256_stream_si256((__m256i*)(out+ppos+32*t),_mm256_load_si256((const __m256i*)(block[bb^1]+32*t)));
 }
 _mm_sfence();
 for(;j<bytes&&pos<total;j+=4){
 uint32_t v;__builtin_memcpy(&v,src+j,4);
 uint64_t a=_pdep_u64(v,mask),b=_pdep_u64(v>>16,mask>>4);
 uint64_t lo=a|carry,hi=b;carry=uint64_t(v>>31)<<1;
 if(pos+16<=total)_mm_storeu_si128((__m128i*)(out+pos),_mm_set_epi64x((long long)hi,(long long)lo));
 else{unsigned char tail[16];__builtin_memcpy(tail,&lo,8);__builtin_memcpy(tail+8,&hi,8);__builtin_memcpy(out+pos,tail,std::min<size_t>(16,total-pos));}
 pos+=15;
 }

 });
 _mm_sfence();out[0]|=0x2c;
 if(n&7)out[total-1]&=(1u<<(n&7))-1;
}

CompilationN/AN/ACompile OKScore: N/A

Testcase #11.298 s1192 MB + 556 KBAcceptedScore: 100


Judge Duck Online | 评测鸭在线
Server Time: 2026-11-18 00:18:02 | Loaded in 15 ms | Server Status
个人娱乐项目,仅供学习交流使用 | 捐赠