package main
import (
	"fmt"
)

type PrimeGenerator struct {
	Next func() uint32
}

func NewPrimeGenerator() *PrimeGenerator {
	primeGenerator := PrimeGenerator{}
	
	multiples := map[uint32]uint32{}
	var num uint32
	primeGenerator.Next = func() uint32 {
		if num == 0 {
			num = 1
			return 2
		}
		
		for ;; {
		    num += 2
		    
			factor, hasFactor := multiples[num]
			if hasFactor {
				delete(multiples, num)
			} else {
				factor = num << 1
			}
		
			for newNum := num + factor; ; newNum += factor {
				_, hasNewFactor := multiples[newNum]
				if !hasNewFactor {
					multiples[newNum] = factor
					break
				}
			}
			
			if !hasFactor {
				return num
			}
		}
	}
	
	return &primeGenerator
}

func main() {
	n := 1000000
	primeGenerator := NewPrimeGenerator()
	for i := 1; i < n; i++ {
		primeGenerator.Next()
	}
	fmt.Printf("%d番目の素数: %d", n, primeGenerator.Next())
}