function basicsieve(n)
  sieve = trues(n)
  sieve[1] = false
  last = Int(ceil(sqrt(n)))
  @inbounds for p in 2:last
    if sieve[p]
      for i in p*p:p:n
        sieve[i] = false
      end
    end
  end
  sieve
end

function sievesegment(sievedprimes,sieve,start) # starts sieving at start + 1
  last = min(Int(ceil(sqrt(start + length(sieve)))) , length(sievedprimes))
  @inbounds for p in 2:last
    if sievedprimes[p]
      for i in (p - start%p):p:length(sieve)
        sieve[i] = false
      end
    end
  end
end


using ResumableFunctions

@resumable function segmentedsieve(n)
    segmentstart = 0
    segmentend = Int(ceil(sqrt(n)))
    initialsieve = basicsieve(segmentend)
    segment = initialsieve
    lastprime = 2
    p = 3

    while p <= n
        while p <= segmentend
            if segment[p-segmentstart]
                @yield lastprime
                lastprime = p
            end
            p+=1
        end
        segmentstart  += length(segment)
        segmentend += length(segment)
        segmentend = min(segmentend,n)
        segment .= true
        sievesegment(initialsieve,segment,segmentstart)
    end
    lastprime
end


function segmentedsieve_channel(n)
    Channel() do c
        segmentstart = 0
        segmentend = Int(ceil(sqrt(n)))
        initialsieve = basicsieve(segmentend)
        segment = initialsieve
        lastprime = 2
        p = 3

        while p <= n
            while p <= segmentend
               if segment[p-segmentstart]
                   push!(c,lastprime)
                   lastprime = p
               end
               p+=1
            end
            segmentstart  += length(segment)
            segmentend += length(segment)
            segmentend = min(segmentend,n)
            segment .= true
            sievesegment(initialsieve,segment,segmentstart)
        end
        push!(c,lastprime)
    end
end


mutable struct Siever
    n::Int
    segmentstart::Int
    segmentend::Int
    initialsieve::BitArray{1}
    segment::BitArray{1}
end

function segmentedsieve_iterator(n)
    last = Int(ceil(sqrt(n)))
    initialsieve = basicsieve(last)
    Siever(n,0,last,initialsieve,initialsieve)
end

function Base.start(s::Siever)
    s.segment .= s.initialsieve
    s.segmentstart = 0
    s.segmentend = length(s.segment)
    2
end

function Base.next(s::Siever,lastprime)
    p = lastprime
    p += 1
    while p <= s.n
        while p <= s.segmentend
            if s.segment[p-s.segmentstart]
                return (lastprime,p)
            end
            p+=1
        end
        if s.segmentend == s.n return (lastprime,s.n + 1) end
        s.segmentstart += length(s.segment)
        s.segmentend += length(s.segment)
        s.segmentend = min(s.segmentend,s.n)
        s.segment .= true
        sievesegment(s.initialsieve,s.segment,s.segmentstart)
    end
    (p-1,s.n+1)
end

Base.done(s::Siever,nextprime) = nextprime > s.n


bench1() = for i in segmentedsieve(n) end
bench2() = for i in segmentedsieve_channel(n) end
bench3() = for i in segmentedsieve_iterator(n) end