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())
}
cGFja2FnZSBtYWluCmltcG9ydCAoCgkiZm10IgopCgp0eXBlIFByaW1lR2VuZXJhdG9yIHN0cnVjdCB7CglOZXh0IGZ1bmMoKSB1aW50MzIKfQoKZnVuYyBOZXdQcmltZUdlbmVyYXRvcigpICpQcmltZUdlbmVyYXRvciB7CglwcmltZUdlbmVyYXRvciA6PSBQcmltZUdlbmVyYXRvcnt9CgkKCW11bHRpcGxlcyA6PSBtYXBbdWludDMyXXVpbnQzMnt9Cgl2YXIgbnVtIHVpbnQzMgoJcHJpbWVHZW5lcmF0b3IuTmV4dCA9IGZ1bmMoKSB1aW50MzIgewoJCWlmIG51bSA9PSAwIHsKCQkJbnVtID0gMQoJCQlyZXR1cm4gMgoJCX0KCQkKCQlmb3IgOzsgewoJCSAgICBudW0gKz0gMgoJCSAgICAKCQkJZmFjdG9yLCBoYXNGYWN0b3IgOj0gbXVsdGlwbGVzW251bV0KCQkJaWYgaGFzRmFjdG9yIHsKCQkJCWRlbGV0ZShtdWx0aXBsZXMsIG51bSkKCQkJfSBlbHNlIHsKCQkJCWZhY3RvciA9IG51bSA8PCAxCgkJCX0KCQkKCQkJZm9yIG5ld051bSA6PSBudW0gKyBmYWN0b3I7IDsgbmV3TnVtICs9IGZhY3RvciB7CgkJCQlfLCBoYXNOZXdGYWN0b3IgOj0gbXVsdGlwbGVzW25ld051bV0KCQkJCWlmICFoYXNOZXdGYWN0b3IgewoJCQkJCW11bHRpcGxlc1tuZXdOdW1dID0gZmFjdG9yCgkJCQkJYnJlYWsKCQkJCX0KCQkJfQoJCQkKCQkJaWYgIWhhc0ZhY3RvciB7CgkJCQlyZXR1cm4gbnVtCgkJCX0KCQl9Cgl9CgkKCXJldHVybiAmcHJpbWVHZW5lcmF0b3IKfQoKZnVuYyBtYWluKCkgewoJbiA6PSAxMDAwMDAwCglwcmltZUdlbmVyYXRvciA6PSBOZXdQcmltZUdlbmVyYXRvcigpCglmb3IgaSA6PSAxOyBpIDwgbjsgaSsrIHsKCQlwcmltZUdlbmVyYXRvci5OZXh0KCkKCX0KCWZtdC5QcmludGYoIiVk55Wq55uu44Gu57Sg5pWwOiAlZCIsIG4sIHByaW1lR2VuZXJhdG9yLk5leHQoKSkKfQ==