fork(2) download
copy 
  1. package main
  2. import (
  3. 	"fmt"
  4. )
  5.  
  6. type PrimeGenerator struct {
  7. 	Next func() uint32
  8. }
  9.  
  10. func NewPrimeGenerator() *PrimeGenerator {
  11. 	primeGenerator := PrimeGenerator{}
  12.  
  13. 	multiples := map[uint32]uint32{}
  14. 	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}
  15. 	var num uint32
  16. 	var i uint32 = 0
  17. 	primeGenerator.Next = func() uint32 {
  18. 		if num == 0 {
  19. 			num = 2
  20. 			return 2
  21. 		}
  22. 		if num == 2 {
  23. 			num = 3
  24. 			return 3
  25. 		}
  26. 		if num == 3 {
  27. 			num = 5
  28. 			return 5
  29. 		}
  30. 		if num == 5 {
  31. 			num = 1
  32. 			return 7
  33. 		}
  34.  
  35. 		for ; ; {
  36. 			num += wheelCycle[i]
  37. 			i = (i + 1) % 48
  38.  
  39. 			factor, hasFactor := multiples[num]
  40. 			var k uint32
  41. 			if hasFactor {
  42. 				delete(multiples, num)
  43.  
  44. 				switch (num / factor) % 210{
  45. 				case 1: k = 0
  46. 				case 11: k = 1
  47. 				case 13: k = 2
  48. 				case 17: k = 3
  49. 				case 19: k = 4
  50. 				case 23: k = 5
  51. 				case 29: k = 6
  52. 				case 31: k = 7
  53. 				case 37: k = 8
  54. 				case 41: k = 9
  55. 				case 43: k = 10
  56. 				case 47: k = 11
  57. 				case 53: k = 12
  58. 				case 59: k = 13
  59. 				case 61: k = 14
  60. 				case 67: k = 15
  61. 				case 71: k = 16
  62. 				case 73: k = 17
  63. 				case 79: k = 18
  64. 				case 83: k = 19
  65. 				case 89: k = 20
  66. 				case 97: k = 21
  67. 				case 101: k = 22
  68. 				case 103: k = 23
  69. 				case 107: k = 24
  70. 				case 109: k = 25
  71. 				case 113: k = 26
  72. 				case 121: k = 27
  73. 				case 127: k = 28
  74. 				case 131: k = 29
  75. 				case 137: k = 30
  76. 				case 139: k = 31
  77. 				case 143: k = 32
  78. 				case 149: k = 33
  79. 				case 151: k = 34
  80. 				case 157: k = 35
  81. 				case 163: k = 36
  82. 				case 167: k = 37
  83. 				case 169: k = 38
  84. 				case 173: k = 39
  85. 				case 179: k = 40
  86. 				case 181: k = 41
  87. 				case 187: k = 42
  88. 				case 191: k = 43
  89. 				case 193: k = 44
  90. 				case 197: k = 45
  91. 				case 199: k = 46
  92. 				case 209: k = 47
  93. 				}
  94. 			} else {
  95. 				factor = num
  96. 			}
  97.  
  98. 			for newNum := num + factor * wheelCycle[k]; ; newNum += factor * wheelCycle[k] {
  99. 				_, hasNewFactor := multiples[newNum]
  100. 				if !hasNewFactor {
  101. 					multiples[newNum] = factor
  102. 					break
  103. 				}
  104. 				k = (k + 1) % 48
  105. 			}
  106.  
  107. 			if !hasFactor {
  108. 				return num
  109. 			}
  110. 		}
  111. 	}
  112.  
  113. 	return &primeGenerator
  114. }
  115.  
  116. func main() {
  117. 	n := 1000000
  118. 	primeGenerator := NewPrimeGenerator()
  119. 	for i := 1; i < n; i++ {
  120. 		primeGenerator.Next()
  121. 	}
  122. 	fmt.Printf("%d番目の素数: %d", n, primeGenerator.Next())
  123. }
Success #stdin #stdout 0.96s 47600KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1000000番目の素数: 15485863
https://ideone.com/qBXbRM
forked from https://i...content-available-to-author-only...e.com/zjVCgk
language:
Go (go 1.12.1)
created:
7 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!