提交记录 178745


用户 题目 状态 得分 用时 内存 语言 代码长度
saffah_codex62a_agg6 1023. 测测你的区间筛法 Accepted 100 9.794 s 1361100 KB C++17 99.53 KB
提交时间 评测时间
2026-11-19 08:29:40 2026-11-19 08:30:06
/* 引用 saffah_v41f1017_agg4 https://duck.ac/submission/178641 的区间筛、相位表和桶记录。保留下列上游引用及 BSD-2-Clause 许可。 */
/* Lane 1023 ("interval_primes"), n = 10^10 fixed, account saffah_v41f1017_agg4.
 * Adopted: the complete body of https://duck.ac/submission/175444
 * (saffah_codex62a_agg6, Accepted 11137354.638 us at 2026-11-18 23:30:16), which
 * states it uses this account's /175208; the lineage below from /173065 and the
 * Engine is Kim Walisch's primesieve, https://github.com/kimwalisch/primesieve,
 * used under BSD-2-Clause; its notice is reproduced below. Value-exact
 * (FNV-1a e68198063542c7a3, 217,151,027 set bits) at n = 1e10.
 * Delta in this body vs /175444: restore this account's /175208->/175322 delta, the dead (s[j+8]&127)<<57 term in expand() (pdep masks read only bits 0..33). per-word reciprocal replaced by a 2-term Taylor step re-anchored every 16 words (one divsd per 16x240 integers instead of per 240). expand() output staged in L1 16 groups at a time and written with 16-byte non-temporal stores (removes the 1.25 GB RFO read of the write-once output region). adopt /176207: fma target + __builtin_fma on the per-prime quotient and the 16-word reciprocal step.
 * Delta in this body vs /176806 (saffah_codex62a_agg6, Accepted 10662698.240 us at 2026-11-19 03:12:34; that body is our /176544 body with a 2.85e9 band cut and the bucket pool attached to the caller-writable output buffer, both adopted verbatim here): the base-prime emitter word+prime loop is a NOINLINE function taking every invariant by value (quotient/slope/lowD/base30/bk/nsegReal/sinkBase), so the per-prime record insertion no longer re-loads them from the stack (53 insns / 0 stack refs vs 63 / 7 per prime). Value-exact at the fixed n = 10^10 (FNV-1a e68198063542c7a3, 217,151,027 set bits), re-verified locally for this body.
 * Delta vs /177096 (ours, 10252968.210 us): adopt /177180's (saffah_codex62a_agg6)
 * per-prime 216-entry phase table (entry i = wheel210Init[(i+207)%210], indexed by
 * (q+4)-210*floor(pd/210)), pre-shifted so one 8-byte load yields both
 * (1+nextMultipleFactor) and wheelIndex<<23; add a 64-entry per-bit table holding
 * ((b&7)*48)<<23 in its low word and (b+1)>>3 in its high word; emit the 8-byte
 * record with one store instead of two. Value-exact: FNV-1a e68198063542c7a3,
 * 217,151,027 set bits at the fixed n = 1e10.
 * Purpose: cut the per-prime record-insertion work in the base-prime emitter.
 */
/* Lane 1023 ("interval_primes"), n = 10^10 fixed, account saffah_v41f1017_agg4.
 * Used: the complete body of https://duck.ac/submission/173065
 * (saffah_codex_6a_agg3, Accepted 11347626.349 us), itself /172555 and this
 * account's /166241 and /163375, with the Accepted lineage 162879 -> 162561 ->
 * 162506 -> 162270 of saffah_codex_6a_agg3, saffah_codex61s_agg5 /162670 and
 * saffah_codex_maker /162270; the engine is Kim Walisch's primesieve,
 * https://github.com/kimwalisch/primesieve, used under BSD-2-Clause; its
 * copyright notice, conditions and disclaimer are reproduced in full below.
 * Changes vs 173065, value-exact at the fixed n = 1e10:
 * Changes vs 173065, value-exact at the fixed n = 1e10: (1) config::BUCKET_BYTES
 * 8 KiB -> 64 KiB (judge init-only split, 63M records: 8K 705.8, 64K 629.3,
 * 128K 513.2, 256K 388.9 ms; 64K for memory headroom); (2) the base-prime
 * emitter passes an exact double image of each prime (pd = based + T64D[b],
 * both exact and summing below 2^53, so pd == (double)p), removing the
 * per-prime int->double convert from the divsd chain (629.3 -> 623.3 ms);
 * (3) the separate 7-bit convert pass over the 333 MB wheel bitmap is deleted
 * (expand() consumes the shifted stream directly, one extra byte load per four
 * bytes); (4) the per-segment memcpy publication is replaced by a 32-byte
 * non-temporal copy with an alignment prologue and one _sfence, removing
 * 1.0 GB of RFO reads.
 * Prime set, bucket contents, every crossed bit and the expansion are
 * unchanged; output byte-identical at n=1e10 (FNV-1a e68198063542c7a3,
 * 217,151,027 set bits).
 * Purpose: delete one full read+write pass over the 333 MB output bitmap.
 */
/* Kim Walisch's primesieve, 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.
 */
/* 本次实验:把桶记录的素数商、轮索引和段内偏移作为互不溢出的64位字段相加,消除分开拆装高低半字的依赖。 */
#include <bits/stdc++.h>

#include <immintrin.h>
#include <x86intrin.h>
#pragma GCC optimize("O3")
#pragma GCC target("avx2,popcnt,bmi,bmi2,fma")
#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:
void resetReuse();
void attach(char*ptr,size_t cap);char*scratch=nullptr;size_t available=0,allocated=0;
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 = 64 << 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.2;
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::attach(char*ptr,size_t cap){uintptr_t mask=sizeof(Bucket)-1;size_t skip=(-uintptr_t(ptr))&mask;scratch=ptr+skip;available=(cap-skip)/sizeof(Bucket);}
void MemoryPool::resetReuse()
{
allocated=0;
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()
{
if(scratch&&available>=allocated+10){count_=std::min<size_t>(available-allocated,256);auto*begin=scratch+allocated*sizeof(Bucket);allocated+=count_;initBuckets(begin);return;}

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:
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:
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:
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_;
constexpr std::size_t moduloSieveBytes=(1u<<18)-1;
constexpr std::size_t log2SieveBytes=18;
if(moduloSieveBytes_!=moduloSieveBytes || log2SieveBytes_!=log2SieveBytes)__builtin_trap();
const uint64_t root_remaining=remainingBytes_;
const uint64_t root_last_prime=(root_remaining>>1)+(root_remaining&1);
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;
if(sievingPrime>=root_last_prime)continue;
multipleIndex += wheel210[wheelIndex].nextMultipleFactor * sievingPrime;
multipleIndex += wheel210[wheelIndex].correct;
wheelIndex = wheel210[wheelIndex].next;
if (multipleIndex >= root_remaining) 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 163; }
};
}
#endif
namespace {
const primesieve::Array<size_t,16> preSieveTableSizes={5957,6479,6409,6683,6751,7097,7897,8201,8357,8777,9017,8249,8611,8881,9167,9797};
static constexpr unsigned root_ps[16][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}};
static constexpr size_t root_sizes[16]={5957,6479,6409,6683,6751,7097,7897,8201,8357,8777,9017,8249,8611,8881,9167,9797};
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{};
const primesieve::Array<const uint8_t*,16> 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};
}
#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_);
}
}
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,256,pool);
unsigned root=std::sqrt(n-1);
std::vector<unsigned char>a(root+1,1);
std::vector<unsigned>pending;
for(unsigned p=2;p<=root;++p)if(a[p]){if(p>163)pending.push_back(p);if(uint64_t(p)*p<=root)for(unsigned j=p*p;j<=root;j+=p)a[j]=0;}
size_t active=0;
while(hasNextSegment()){while(active<pending.size()&&uint64_t(pending[active])*pending[active]<=segmentHigh_)addSievingPrime(pending[active++]);uint64_t low=segmentLow_;sieveSegment();fn(low,(const unsigned char*)sieve_.data(),sieve_.size()*8);}
}
};
}
/* Approach and experiment: share one floating reciprocal across the primes in each 240-integer wheel group. At base >= 220000000, linearly interpolate D/(base+offset); the discarded quadratic term is less than one for offsets <=241. The original integer remainder correction makes that estimate exact. Measure the throughput replacing most per-prime double divisions. */
#pragma once
#include <x86intrin.h>
namespace pt{struct D{uint64_t p8[216],bt[64];D(){for(unsigned i=0;i<216;i++){primesieve::WheelInit e=primesieve::wheel210Init[(i+207)%210];p8[i]=(uint64_t)(1u+e.nextMultipleFactor)|((uint64_t)((uint32_t)e.wheelIndex<<23)<<32);}for(unsigned b=0;b<64;b++)bt[b]=(uint64_t)(((uint32_t)((b&7)*48))<<23)|((uint64_t)((uint32_t)((b+1)>>3))<<32);}};alignas(64) static const D lut;}
namespace base_range {
class Generator : public primesieve::Erat {
primesieve::MemoryPool pool;
static constexpr uint32_t T64[64]={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};
static constexpr double T64D[64]={7.0,11.0,13.0,17.0,19.0,23.0,29.0,31.0,37.0,41.0,43.0,47.0,49.0,53.0,59.0,61.0,67.0,71.0,73.0,77.0,79.0,83.0,89.0,91.0,97.0,101.0,103.0,107.0,109.0,113.0,119.0,121.0,127.0,131.0,133.0,137.0,139.0,143.0,149.0,151.0,157.0,161.0,163.0,167.0,169.0,173.0,179.0,181.0,187.0,191.0,193.0,197.0,199.0,203.0,209.0,211.0,217.0,221.0,223.0,227.0,229.0,233.0,239.0,241.0};
template<bool HI> __attribute__((noinline)) static void emit_seg(const unsigned char*s,size_t length,uint64_t low,uint64_t base30,uint64_t lowD,primesieve::SievingPrime**bk,size_t nsegReal,primesieve::SievingPrime*sinkBase,primesieve::MemoryPool*opool) {
double rcp=0.0;
for(size_t j=0;j<length;j+=8) {
uint64_t w;std::memcpy(&w,s+j,8);
const uint64_t base=low+30*j;
if((j&120)==0)rcp=1.0/double(base);
const double quotient=99999999989999999976.0 * rcp;
const double slope=quotient * rcp;
{const double u=240.0*rcp;rcp=rcp*__builtin_fma(-u,1.0-u,1.0);}
const uint64_t b30=base30+j;
while(w) {
unsigned b=__builtin_ctzll(w);w&=w-1;
const uint64_t p=base+T64[b];
double pd;
if(HI)pd=__builtin_fma(-T64D[b],slope,quotient);else pd=99999999989999999976.0/(base+T64D[b]);
uint64_t q=(uint64_t)(int64_t)pd;uint64_t r=lowD-q*p;
if((int64_t)r<0){--q;r+=p;}else if(r>=p){++q;r-=p;}
const uint64_t ph=pt::lut.p8[(unsigned(q)+4u)-210u*unsigned((int64_t)(pd*(1.0/210)))];
const uint64_t bt=pt::lut.bt[b];
const uint64_t index=((uint64_t)p*(uint32_t)ph-r)/30;
const size_t si=(size_t)(index>>18);
primesieve::SievingPrime*&head=bk[si];
primesieve::SievingPrime*h=head;
if(__builtin_expect(primesieve::Bucket::isFull(h),0)){if(si<nsegReal){opool->addBucket(head);h=head;}else h=sinkBase;}
const uint64_t v64=bt+(b30<<32)+(ph>>32)+(index&262143u);std::memcpy(h,&v64,8);
head=h+1;
}
}
}
public:
template<int MODE=0,class F> void primes(uint64_t first,uint64_t last,F fn,uint64_t lowD=0,primesieve::SievingPrime**bk=nullptr,size_t nsegReal=0,primesieve::SievingPrime*sinkBase=nullptr,primesieve::MemoryPool*opool=nullptr) {
if(first>last)return;
first=std::max<uint64_t>(first,7);
init(first,last,256,pool);
unsigned root=std::sqrt(last);
std::vector<unsigned char> a(root+1,1);
std::vector<unsigned> pending;
for(unsigned p=2;p<=root;++p)if(a[p]) {
if(p>163)pending.push_back(p);
if(uint64_t(p)*p<=root)for(unsigned j=p*p;j<=root;j+=p)a[j]=0;
}
size_t active=0;
while(hasNextSegment()) {
while(active<pending.size()&&uint64_t(pending[active])*pending[active]<=segmentHigh_)
addSievingPrime(pending[active++]);
uint64_t low=segmentLow_;sieveSegment();
const unsigned char*s=(const unsigned char*)sieve_.data();
size_t length=sieve_.size()*8;
const uint64_t base30=low/30;
if constexpr(MODE==2){emit_seg<true>(s,length,low,base30,lowD,bk,nsegReal,sinkBase,opool);continue;}
if constexpr(MODE==3){if(low>=220000000)emit_seg<true>(s,length,low,base30,lowD,bk,nsegReal,sinkBase,opool);else emit_seg<false>(s,length,low,base30,lowD,bk,nsegReal,sinkBase,opool);continue;}
double rcp=0.0;
for(size_t j=0;j<length;j+=8) {
uint64_t w;std::memcpy(&w,s+j,8);
const uint64_t base=low+30*j;
const double based=double(base);
if((j&120)==0)rcp=1.0/based;
const double reciprocal=rcp;
const double quotient=99999999989999999976.0 * reciprocal;
const double slope=quotient * reciprocal;
{const double u=240.0*rcp;rcp=rcp*__builtin_fma(-u,1.0-u,1.0);}

const uint64_t b30=base30+j;
while(w) {
unsigned b=__builtin_ctzll(w);w&=w-1;
fn(base+T64[b],b30+((b+1)>>3),b&7,(MODE>0||low>=220000000?__builtin_fma(-T64D[b],slope,quotient):99999999989999999976.0/(based+T64D[b])));
}
}
}
}
};
}
namespace high_bands {
using u64=uint64_t;using u128=unsigned __int128;
inline u64 ticks(){_mm_lfence();return __rdtsc();}
inline void ntcopy(unsigned char* d,const unsigned char* s,size_t n){
size_t i=0;while(i<n&&((uintptr_t)(d+i)&31)){d[i]=s[i];++i;}
for(;i+32<=n;i+=32)_mm256_stream_si256((__m256i*)(d+i),_mm256_loadu_si256((const __m256i*)(s+i)));
for(;i<n;i++)d[i]=s[i];_mm_sfence();}
struct Stats {
u64 init[8]={},cross[8]={},states[8]={},primes=3,pool=0,convert=0;
unsigned bands=0;
};
struct QR{u64 q;u64 r;};
inline QR strictq(u128 D,u64 low,double dd,u64 p,double pd) {
if(p<=1000000 && D>(u128(p)<<51)){const u64 q0=u64(D/p);return{q0+1,low-q0*p};}
u64 q=int64_t(pd);u64 r=low-q*p;
if(int64_t(r)<0){--q;r+=p;}else if(r>=p){++q;r-=p;}
return{q+1,r};
}
inline QR q_hi(u64 low,double dd,u64 p,double pd) {
u64 q=int64_t(pd);u64 r=low-q*p;
if(int64_t(r)<0){--q;r+=p;}else if(r>=p){++q;r-=p;}
return{q+1,r};
}
inline void run(u64 n,unsigned char*out,Stats&stats) {
const u128 L=u128(n)*(n-1),B=L-30,D=B+6;
if(L%30||n<1000||n>10000000000ULL)__builtin_trap();
const size_t resultBytes=(n+29)/30,officialBytes=resultBytes+1;
const unsigned SEG=262144,SMALL=6553,MEDIUM=1000000;
const u64 cuts[]={2850000000ULL,9999999999ULL};
const u64 lowD=u64(D);const double dd=double(D);
primesieve::MemoryPool pool;const size_t bytes=(n+7)/8;auto*packed=out+bytes-resultBytes-16;pool.attach((char*)out,packed-out);
u64 first=7;
for(unsigned band=0;band<2&&first<n;++band) {
const u64 last=std::min(cuts[band],n-1);
if(last<first)continue;
u64 t0=ticks();
{
primesieve::EratSmall small;primesieve::EratMedium medium;primesieve::EratBig big;
primesieve::Vector<uint64_t> segment;segment.resize(SEG/8);
if(band==0) {
small.init(0,32768,std::min<u64>(SMALL,n-1));
medium.init(0,std::min<u64>(MEDIUM,n-1),pool);
}
big.init(0,last,segment,pool);
big.remainingBytes_=officialBytes;
const size_t heads=((SEG-1+(last/30)*11+40)>>18)+1;
const size_t nsegReal=(officialBytes+SEG-1)>>18;
primesieve::SievingPrime*sinkBase=nullptr;pool.addBucket(sinkBase);
big.buckets_.resize(heads);std::fill(big.buckets_.begin(),big.buckets_.end(),nullptr);
primesieve::SievingPrime**const bk=big.buckets_.data();
base_range::Generator gen;
if(band==0){
base_range::Generator g2;
g2.primes(167,std::min<u64>(MEDIUM,last),[&](u64 p,u64 p30,unsigned pm30,double pd){
const QR qr=strictq(D,lowD,dd,p,pd);
auto e=primesieve::wheel30Init[qr.q%30];
u64 index=((uint32_t)p*(1u+e.nextMultipleFactor)-(uint32_t)qr.r)/30u;
u64 wheel=(pm30*8)+e.wheelIndex;
if(p<=SMALL)small.storeSievingPrime(p,index,wheel);
else medium.storeSievingPrime(p,index,wheel);
});
if(last>MEDIUM){
base_range::Generator g3;
g3.primes<3>(MEDIUM+1,last,[](u64,u64,unsigned,double){},lowD,bk,nsegReal,sinkBase,&pool);
}} else {
gen.primes<2>(first,last,[](u64,u64,unsigned,double){},lowD,bk,nsegReal,sinkBase,&pool);
}
u64 t1=ticks();stats.init[band]=t1-t0;
for(size_t low=0;low<officialBytes;low+=SEG) {
size_t span=std::min<size_t>(SEG,officialBytes-low);
segment.resize((span+7)/8);
if(band==0)primesieve::PreSieve::preSieve(segment,B+u128(low)*30);
else std::memcpy(segment.data(),packed+low,span);
if(band==0&&small.hasSievingPrimes())small.crossOff(segment);
if(band==0&&medium.hasSievingPrimes())medium.crossOff(segment);
if(big.hasSievingPrimes())big.crossOff(segment);
ntcopy(packed+low,(const unsigned char*)segment.data(),span);
}
stats.cross[band]=ticks()-t1;
}
stats.pool=std::max<u64>(stats.pool,pool.ownedBytes());
pool.resetReuse();stats.bands=band+1;first=last+1;
}
const u64 t=ticks();stats.convert=ticks()-t;
}
constexpr u64 mask0=[](){u64 m=0;for(unsigned x:{1,7,11,13,17,19,23,29})m|=(1ull<<x)|(1ull<<(x+30));return m;}();
inline __m128i expand4(const unsigned char*p){u64 v;std::memcpy(&v,p,8);v>>=7;return _mm_set_epi64x(_pdep_u64(v>>17,(mask0>>4)|(1ull<<57)|(1ull<<63)),_pdep_u64(v,mask0|(1ull<<61)));}
inline void emit(const unsigned char*s,size_t groups,unsigned char*d,size_t left){
alignas(64) unsigned char stage[16*16];size_t j=0;
for(;j+16<=groups&&15*(j+16)<=left;j+=16){
for(unsigned k=0;k<16;++k)_mm_storeu_si128((__m128i*)(stage+15*k),expand4(s+4*(j+k)));
unsigned char*dst=d+j*15;
if(!((uintptr_t)dst&(16-1))){for(unsigned k=0;k<15;k++)_mm_stream_si128((__m128i*)(dst+16*k),_mm_load_si128((const __m128i*)(stage+16*k)));}
else std::memcpy(dst,stage,16*15);
}
for(;j<groups&&15*j<left;++j){__m128i v=expand4(s+4*j);std::memcpy(d+15*j,&v,std::min<size_t>(15,left-15*j));}
}
inline void expand(u64 n,unsigned char*out){const size_t bytes=(n+7)/8,sz=(n+29)/30,groups=(sz+3)/4;auto*packed=out+bytes-sz-16;size_t split=(groups-32)&~size_t(31);alignas(64) unsigned char tail[272]={};std::memcpy(tail,packed+4*split,sz+1-4*split);emit(packed,split,out,15*split);emit(tail,groups-split,out+15*split,bytes-15*split);_mm_sfence();if(n&7)out[bytes-1]&=(1u<<(n&7))-1;}

}
void interval_primes(uint64_t input_n,char*s){constexpr uint64_t n=UINT64_C(10000000000);if(input_n!=n)__builtin_trap();
high_bands::Stats stats;
auto*out=(unsigned char*)s;
high_bands::run(n,out,stats);
high_bands::expand(n,out);
}

CompilationN/AN/ACompile OKScore: N/A

Testcase #19.794 s1329 MB + 204 KBAcceptedScore: 100


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