Feature request: lazy iterator API for `nextprime` / `prevprime`

[s-celles]

Hello,

The current nextprime(n, i) and prevprime(n, i) API works but does not
compose naturally with Julia's iterator ecosystem. I'd like to propose adding
a lazy iterator - backed by a single type PrimeIterator{T, Up} — that
integrates directly with Iterators.take, Iterators.takewhile, filter,
zip, and the rest of Base.Iterators.

Motivation

The current API forces the caller to either call nextprime in a manual loop,
or pass an explicit count i to simulate iteration. Neither approach composes
well with Julia idioms. Compare:

# Current — manual simulation of iteration
[nextprime(100, i) for i in 1:10]

# Proposed — lazy, composable, no allocation
collect(Iterators.take(primes_from(100), 10))

Patterns that are natural in Julia today become awkward or impossible without a
true iterator:

# First prime ≥ 1_000_000 with p ≡ 1 (mod 4)
first(p for p in primes_from(1_000_000) if p % 4 == 1)

# Twin prime candidates — no intermediate allocation
zip(primes_from(2), Iterators.drop(primes_from(2), 1))

# Sum of primes in [lo, hi] — lazy, no sieve needed
sum(Iterators.takewhile(<=(hi), primes_from(lo)))

# Descending from a starting point
collect(Iterators.take(primes_upto(200), 5))
# [199, 197, 193, 191, 181]

Proposed implementation

A single parametric type covers both directions. The Up boolean parameter is
resolved at compile time — no runtime branching, no overhead.

struct PrimeIterator{T<:Integer, Up}
    start::T
end

# Public constructors
primes_from(n::T) where T<:Integer = PrimeIterator{T, true}(n)
primes_from()                      = PrimeIterator{Int, true}(2)
primes_upto(n::T)  where T<:Integer = PrimeIterator{T, false}(n)

# IteratorSize — differs by direction, dispatched on the type parameter
Base.IteratorSize(::Type{<:PrimeIterator{T, true}})  where T = Base.IsInfinite()
Base.IteratorSize(::Type{<:PrimeIterator{T, false}}) where T = Base.SizeUnknown()
Base.eltype(::Type{<:PrimeIterator{T}})              where T = T

# iterate — ascending
Base.iterate(it::PrimeIterator{T, true}) where T =
    (p = nextprime(it.start); (p, p))
Base.iterate(::PrimeIterator{T, true}, prev) where T =
    (p = nextprime(prev + one(T)); (p, p))

# iterate — descending
Base.iterate(it::PrimeIterator{T, false}) where T =
    it.start < 2 ? nothing : (p = prevprime(it.start); (p, p))
Base.iterate(::PrimeIterator{T, false}, prev) where T =
    prev <= 2 ? nothing : (p = prevprime(prev - one(T)); (p, p))

REPL display

The Up boolean is an implementation detail. A custom show makes the
iterator self-describing at the REPL, following the same convention as
StepRange (which displays as 1:2:10, not StepRange{Int64,Int64}(1,2,10)):

Base.show(io::IO, it::PrimeIterator{T, true})  where T =
    print(io, "primes_from(", it.start, ")")
Base.show(io::IO, it::PrimeIterator{T, false}) where T =
    print(io, "primes_upto(", it.start, ")")

julia> primes_from(100)
primes_from(100)

julia> primes_upto(50)
primes_upto(50)

julia> typeof(primes_from(100))
PrimeIterator{Int64, true}

Compatibility

• nextprime(n), nextprime(n, i), prevprime(n), prevprime(n, i) are
  fully preserved — no breaking changes.
• The identity nextprime(n, i) == last(Iterators.take(primes_from(n), i))
  holds for all valid inputs and can serve as a property-based test.
• BigInt support is inherited for free: the iterators delegate entirely to
  the existing nextprime/prevprime implementations.
• Both iterators are type-stable: eltype is T, inferred from the
  construction argument. No Any types, no hidden allocations per step.

What this does NOT do

• Does not replace primes(lo, hi) for dense bounded enumeration — the sieve
  remains more efficient there.
• Does not change isprime, factor, or any other existing function.

Open questions

1. Should primes_from / primes_upto be exported at the top level, or
   introduced first as unexported utilities?
2. Should nextprimes(n) (strictly > n, excluding n even if prime) be a
   separate constructor, or is primes_from(nextprime(n+1)) sufficient?

References

• Current nextprime docs: https://juliamath.github.io/Primes.jl/stable/
• Julia iterator interface: https://docs.julialang.org/en/v1/manual/interfaces/#man-interface-iteration
• Prior art: PrimeSieve.jl exposes allprimes() and someprimes(lo, hi) as
  lazy iterators with a similar motivation.

[s-celles]

Here is a spec proposal to be discussed

Lazy Prime Iterator API for Primes.jl

1. Core Iterator Construction

REQ-01
: The system shall produce prime numbers starting from the smallest prime
greater than or equal to n when primes_from(n) is called.

REQ-02
: The system shall produce prime numbers in descending order starting from the
largest prime less than or equal to n when primes_upto(n) is called.

REQ-03
: When primes_from() is called with no argument, the system shall start
iteration from 2.

---

2. Unified Internal Representation

REQ-04
: The system shall represent both ascending and descending iterators as a
single parametric type PrimeIterator{T<:Integer, Up}, where Up is a
boolean type parameter resolved at compile time.

REQ-05
: primes_from(n::T) shall construct PrimeIterator{T, true}(n).

REQ-06
: primes_upto(n::T) shall construct PrimeIterator{T, false}(n).

---

3. Termination and Size

REQ-07
: The primes_from iterator shall be declared Base.IsInfinite and shall
never return nothing on its own.

REQ-08
: The primes_upto iterator shall be declared Base.SizeUnknown and shall
return nothing and terminate when the current candidate falls below 2.

---

4. Element Type

REQ-09
: The iterator shall preserve the integer type T of its construction
argument throughout iteration, such that
eltype(primes_from(n::T)) == eltype(primes_upto(n::T)) == T.

REQ-10
: If T is BigInt, the iterator shall yield pseudo-prime values consistent
with the behavior of the underlying nextprime and prevprime functions.

---

5. Composability with Base.Iterators

REQ-11
: The iterator shall be usable with Iterators.take(primes_from(n), k) to
lazily produce the k smallest primes greater than or equal to n.

REQ-12
: The iterator shall be usable with Iterators.take(primes_upto(n), k) to
lazily produce the k largest primes less than or equal to n.

REQ-13
: The iterator shall be usable with Iterators.takewhile(pred, primes_from(n))
to lazily filter ascending primes by an arbitrary predicate.

REQ-14
: When composed with Iterators.zip, two prime iterators shall produce pairs
of simultaneous primes without materializing either sequence.

REQ-15
: first(primes_from(n)) shall return the same value as nextprime(n).

REQ-16
: first(primes_upto(n)) shall return the same value as prevprime(n).

---

6. REPL Display

REQ-17
: The system shall implement Base.show such that a PrimeIterator{T, true}
displays as primes_from(<start>) in the REPL.

REQ-18
: The system shall implement Base.show such that a PrimeIterator{T, false}
displays as primes_upto(<start>) in the REPL.

REQ-19
: typeof(primes_from(n)) shall display the internal type
PrimeIterator{T, true}, keeping the boolean parameter visible for
introspection while show provides the user-facing representation.

---

7. Error Handling

REQ-20
: If n is negative, the iterator shall throw an ArgumentError with a
descriptive message.

REQ-21
: When primes_upto(n) is called with n < 2, the iterator shall
immediately terminate without yielding any element.

REQ-22
: If the underlying nextprime or prevprime call overflows the type T,
the iterator shall propagate the resulting OverflowError unmodified.

---

8. Compatibility

REQ-23
: The existing functions nextprime(n), nextprime(n, i), prevprime(n),
and prevprime(n, i) shall remain available and unmodified.

REQ-24
: For all valid inputs, nextprime(n, i) shall return the same value as
last(Iterators.take(primes_from(n), i)).

[oscardssmith]

At some point I would like to do a fairly significant refactor to unify the code paths for nextprime and primes. Specifically, both should be iterator based and choose between a sieve method vs isprime checks based on the width of the interval that the user cares about.

[s-celles]

That's exactly the direction this proposal is trying to enable. The public API (primes_from / primes_upto) is intentionally agnostic about the internal strategy - the PrimeIterator type would just be the stable user-facing contract, while the implementation of iterate is free to switch between isprime checks and a segmented sieve based on observed consumption.

Concretely, nothing in the proposed interface prevents a future iterate from looking like:

function Base.iterate(it::PrimeIterator{T, true}, state) where T
    # if state reveals a wide interval is being consumed,
    # switch to sieve-backed block iteration transparently
end

The user never sees the difference. primes_from(lo) and Iterators.takewhile(<=(hi), primes_from(lo)) stay valid regardless of what happens underneath.

So rather than blocking on the refactor, this PR could land as a thin isprime-based implementation first, with the adaptive sieve slotted in later - same interface, better engine. Would that sequencing work for you?

[s-celles]

The key efficiency of a segmented sieve is that the small primes (all primes ≤ √hi) only need to be computed once upfront, then reused to strike out composites in every subsequent block:

struct PrimeIteratorState{T}
    block        :: Vector{Bool}  # current sieve block, sized to fit in L1/L2 cache
    block_start  :: T             # absolute offset of block[1]
    index        :: Int           # current position within the block
    small_primes :: Vector{T}     # precomputed once, reused across ALL blocks
end

small_primes is allocated once at iterator construction, then every call to iterate that exhausts the current block just sieves a fresh block using the same small_primes — no recomputation, no growing allocations. Each block is consumed and discarded. Memory usage stays constant regardless of how far along the number line you iterate.