Snippets

cia_rana Prime Number Generator with Sieve of Eratosthenes in Golang

Created by cia_rana last modified
primeGenerator.clojure.go
Raw 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
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())
	}
}
primeGenerator.clojure_2_3_5_7.go
Raw 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
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())
}
primeGenerator.go
Raw 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
// # 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())
	}
}
primeGenerator_channel_2_3_5_7.go
Raw 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
// # 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{}
	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())
}

Comments (0)

HTTPS SSH

You can clone a snippet to your computer for local editing. Learn more.