#!/usr/bin/env python
"""\
primes.py -- Generate primes using a heap of primes as the sieve.
Number of tests for a candidate for a prime should be like
    log(n)  where n is the number of primes < sqrt( candidate ).
    (I.e. log(pi(sqrt(candidate)))?
     ~= log( sqrt(candidate) / log(sqrt(candidate)) )?
This is based on primes/prime_heap.py.
Copyright (c) 2020 Steve Witham ess_double_you_at_tiac_notthis_dot_net
BSD license https://opensource.org/licenses/BSD-2-Clause
"""

from __future__ import print_function

def prime_gen( ):
    """\
    Internally this sieve generates all the odd *composites*, 
    and whenever it sees that it missed one, that's a prime.
    Heap-o-Primes using p**3 trick
    Puts all primes in a heapsort-style heap that is not rearranged.
    Each prime entry remembers the next composite for me and next for my subtree.
    The idea is for each prime to try not to generate composites that are
    generated by primes less than itself.
    In this case each prime p generates composites p**2, 
        then p*q, p*r, p*s... where p < primes q, r, s... < p**2,
        then p**3, p**3 + 2p, p**3 + 4p, p**3 + 6p...
    """
    yield 2
    yield 3
    primes = [ 3 ]
    next_multiple_me = [ 9 ]
    next_multiple_subtree = [ 9 ]
    my_j = [ 0 ]
    candidate = 5
    n = 1
    prev = 3
    while True:
        if candidate < next_multiple_subtree[ 0 ]:
            yield candidate

            primes.append( candidate )
            next_multiple_me.append( candidate**2 )
            next_multiple_subtree.append( candidate**2 )
            my_j.append( n )
            n += 1
            prev = candidate
        else:
            i = 0
            while True:
                if next_multiple_me[ i ] == candidate:
                    j = my_j[ i ] + 1
                    p = primes[ i ]
                    if j > 1:
                        q = primes[ j ]
                        if q < p**2:
                            my_j[ i ] = j
                            next_multiple_me[ i ] = p * q
                        else:
                            my_j[ i ] = 0
                            next_multiple_me[ i ] = p**3
                    else:
                        next_multiple_me[ i ] += p * 2

                newnext = next_multiple_me[ i ]
                lefty = i * 2 + 1
                if lefty < n:
                    leftnext = next_multiple_subtree[ lefty ]
                    if leftnext == candidate:
                        i = lefty
                        continue  # Go down to left child.
                    
                    if leftnext < newnext:
                        newnext = leftnext

                righty = lefty + 1
                if righty < n:
                    rightnext = next_multiple_subtree[ righty ]
                    if rightnext == candidate:
                        i = righty
                        continue  # Go down to right child.
                    
                    if rightnext < newnext:
                        newnext = rightnext

                next_multiple_subtree[ i ] = newnext
                if i > 0:
                    i = ( i - 1 ) // 2  # Go up to parent.
                else:
                    break
       
        candidate += 2


def print_primes():
    from sys import exit as _exit, stderr as _stderr
    #  from sys import stdout
    
    # print("hello", file=_stderr)
    try:
        for p in prime_gen():
            print(p, flush=True)
    except (BrokenPipeError, IOError):
        _stderr.close()  # Prevent error messages from coming out.
        _exit()          # Don't let the caller continue without stderr?

if __name__ == "__main__":
    from sys import stderr as _stderr
    if True:
        print_primes()