Created
May 29, 2017 18:54
-
-
Save cia-rana/6ff24dc9c7e28067373a401a539aab16 to your computer and use it in GitHub Desktop.
Prime Number Generator with Sieve of Eratosthenes in Golang
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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() { | |
primeGenerator := NewPrimeGenerator() | |
for i := 1; i <= 100; i++ { | |
fmt.Println(primeGenerator.Next()) | |
} | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
package main | |
import ( | |
"fmt" | |
) | |
type PrimeGenerator struct { | |
next func() uint32 | |
} | |
func NewPrimeGenerator() *PrimeGenerator { | |
primeGenerator := PrimeGenerator{} | |
multiples := map[uint32]uint32{} | |
wheelCycle := []uint32{10, 2, 4, 2, 4, 6, 2, 6, 4, 2, 4, 6, 6, 2, 6, 4, 2, 6, 4, 6, 8, 4, 2, 4, 2, 4, 8, 6, 4, 6, 2, 4, 6, 2, 6, 6, 4, 2, 4, 6, 2, 6, 4, 2, 4, 2, 10, 2} | |
wheelCycleIndices := []uint32{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 2, 0, 0, 0, 3, 0, 4, 0, 0, 0, 5, 0, 0, 0, 0, 0, 6, 0, 7, 0, 0, 0, 0, 0, 8, 0, 0, 0, 9, 0, 10, 0, 0, 0, 11, 0, 0, 0, 0, 0, 12, 0, 0, 0, 0, 0, 13, 0, 14, 0, 0, 0, 0, 0, 15, 0, 0, 0, 16, 0, 17, 0, 0, 0, 0, 0, 18, 0, 0, 0, 19, 0, 0, 0, 0, 0, 20, 0, 0, 0, 0, 0, 0, 0, 21, 0, 0, 0, 22, 0, 23, 0, 0, 0, 24, 0, 25, 0, 0, 0, 26, 0, 0, 0, 0, 0, 0, 0, 27, 0, 0, 0, 0, 0, 28, 0, 0, 0, 29, 0, 0, 0, 0, 0, 30, 0, 31, 0, 0, 0, 32, 0, 0, 0, 0, 0, 33, 0, 34, 0, 0, 0, 0, 0, 35, 0, 0, 0, 0, 0, 36, 0, 0, 0, 37, 0, 38, 0, 0, 0, 39, 0, 0, 0, 0, 0, 40, 0, 41, 0, 0, 0, 0, 0, 42, 0, 0, 0, 43, 0, 44, 0, 0, 0, 45, 0, 46, 0, 0, 0, 0, 0, 0, 0, 0, 0, 47} | |
var num uint32 | |
var i uint32 | |
primeGenerator.next = func() uint32 { | |
if num == 0 { | |
num = 2 | |
return 2 | |
} | |
if num == 2 { | |
num = 3 | |
return 3 | |
} | |
if num == 3 { | |
num = 5 | |
return 5 | |
} | |
if num == 5 { | |
num = 1 | |
return 7 | |
} | |
for ; ; { | |
num += wheelCycle[i] | |
i = (i + 1) % 48 | |
factor, hasFactor := multiples[num] | |
var j uint32 | |
if hasFactor { | |
delete(multiples, num) | |
j = wheelCycleIndices[(num / factor) % 210] | |
} else { | |
factor = num | |
} | |
for newNum := num + factor * wheelCycle[j]; ; newNum += factor * wheelCycle[j] { | |
_, hasNewFactor := multiples[newNum] | |
if !hasNewFactor { | |
multiples[newNum] = factor | |
break | |
} | |
j = (j + 1) % 48 | |
} | |
if !hasFactor { | |
return num | |
} | |
} | |
} | |
return &primeGenerator | |
} | |
func (p *PrimeGenerator) Next() uint32 { | |
return p.next() | |
} | |
func main() { | |
n := 1000000 | |
primeGenerator := NewPrimeGenerator() | |
for i := 1; i < n; i++ { | |
primeGenerator.Next() | |
} | |
fmt.Printf("%d番目の素数: %d", n, primeGenerator.Next()) | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// # Prime Number Generator with Sieve of Eratosthenes in Golang | |
// | |
// ## Usage | |
// Please see the main function below. | |
// | |
// ## Reference | |
// - [The Genuine Sieve of Eratosthenes](https://www.cs.hmc.edu/~oneill/papers/Sieve-JFP.pdf) | |
// - [C#で「エラトステネスの篩」で「2.6秒で百万個」の素数を計算できる「無限シーケンス」を作ってみた - tail-island](https://tail-island.github.io/programming/2016/04/15/lazy-primes.html) | |
package main | |
import ( | |
"fmt" | |
) | |
type PrimeGenerator struct { | |
primeChan chan uint32 | |
} | |
func NewPrimeGenerator() *PrimeGenerator { | |
primeGenerator := PrimeGenerator{ | |
primeChan: make(chan uint32), | |
} | |
go primeGenerator.start() | |
return &primeGenerator | |
} | |
func (p *PrimeGenerator) start() { | |
multiples := map[uint32]uint32{} | |
p.primeChan <- 2 | |
for num := uint32(3); ; 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 { | |
p.primeChan <- num | |
} | |
} | |
} | |
func (p *PrimeGenerator) Next() uint32 { | |
return <- p.primeChan | |
} | |
func main() { | |
primeGenerator := NewPrimeGenerator() | |
for i := 1; i <= 100; i++ { | |
fmt.Println(primeGenerator.Next()) | |
} | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
package main | |
import ( | |
"fmt" | |
) | |
type PrimeGenerator struct { | |
primeChan chan uint32 | |
} | |
func NewPrimeGenerator() *PrimeGenerator { | |
primeGenerator := PrimeGenerator{ | |
primeChan: make(chan uint32), | |
} | |
go primeGenerator.start() | |
return &primeGenerator | |
} | |
func (p *PrimeGenerator) start() { | |
multiples := map[uint32]uint32{} | |
wheelCycle := []uint32{10, 2, 4, 2, 4, 6, 2, 6, 4, 2, 4, 6, 6, 2, 6, 4, 2, 6, 4, 6, 8, 4, 2, 4, 2, 4, 8, 6, 4, 6, 2, 4, 6, 2, 6, 6, 4, 2, 4, 6, 2, 6, 4, 2, 4, 2, 10, 2} | |
wheelCycleIndices := []uint32{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 2, 0, 0, 0, 3, 0, 4, 0, 0, 0, 5, 0, 0, 0, 0, 0, 6, 0, 7, 0, 0, 0, 0, 0, 8, 0, 0, 0, 9, 0, 10, 0, 0, 0, 11, 0, 0, 0, 0, 0, 12, 0, 0, 0, 0, 0, 13, 0, 14, 0, 0, 0, 0, 0, 15, 0, 0, 0, 16, 0, 17, 0, 0, 0, 0, 0, 18, 0, 0, 0, 19, 0, 0, 0, 0, 0, 20, 0, 0, 0, 0, 0, 0, 0, 21, 0, 0, 0, 22, 0, 23, 0, 0, 0, 24, 0, 25, 0, 0, 0, 26, 0, 0, 0, 0, 0, 0, 0, 27, 0, 0, 0, 0, 0, 28, 0, 0, 0, 29, 0, 0, 0, 0, 0, 30, 0, 31, 0, 0, 0, 32, 0, 0, 0, 0, 0, 33, 0, 34, 0, 0, 0, 0, 0, 35, 0, 0, 0, 0, 0, 36, 0, 0, 0, 37, 0, 38, 0, 0, 0, 39, 0, 0, 0, 0, 0, 40, 0, 41, 0, 0, 0, 0, 0, 42, 0, 0, 0, 43, 0, 44, 0, 0, 0, 45, 0, 46, 0, 0, 0, 0, 0, 0, 0, 0, 0, 47} | |
p.primeChan <- 2 | |
p.primeChan <- 3 | |
p.primeChan <- 5 | |
p.primeChan <- 7 | |
num := uint32(1) | |
for i := uint32(0); ; i = (i + 1) % 48 { | |
num += wheelCycle[i] | |
factor, hasFactor := multiples[num] | |
var j uint32 | |
if hasFactor { | |
delete(multiples, num) | |
j = wheelCycleIndices[(num / factor) % 210] | |
} else { | |
factor = num | |
} | |
for newNum := num + factor * wheelCycle[j]; ; newNum += factor * wheelCycle[j] { | |
_, hasNewFactor := multiples[newNum] | |
if !hasNewFactor { | |
multiples[newNum] = factor | |
break | |
} | |
j = (j + 1) % 48 | |
} | |
if !hasFactor { | |
p.primeChan <- num | |
} | |
} | |
} | |
func (p *PrimeGenerator) Next() uint32 { | |
return <- p.primeChan | |
} | |
func main() { | |
primeGenerator := NewPrimeGenerator() | |
for i := 1; i < 100000; i++ { | |
//fmt.Println(primeGenerator.Next()) | |
primeGenerator.Next() | |
} | |
fmt.Println(primeGenerator.Next()) | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment