JuliaMath / JuliaMath/Primes.jl
Feature request: lazy iterator API for `nextprime` / `prevprime`
- Dominant language
- Julia
- Stars
- 108
- Forks
- 34
- PR merge metrics
- No merged PRs in 30d
Description
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:
```julia
# 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:
```julia
# 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.
```julia
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)`):
```julia
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.
Contributor guide
No contributing guide indexed for this repository
Assessment
This issue has not been assessed yet.