fork(1) 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. 	var num uint32
  15. 	var d uint32
  16. 	primeGenerator.Next = func() uint32 {
  17. 		if num == 0 {
  18. 			num = 1
  19. 			return 2
  20. 		}
  21. 		if d == 0 {
  22. 			d = 4
  23. 			return 3
  24. 		}
  25.  
  26. 		for ;; {
  27. 		    num += d
  28. 		    d = 6 - d
  29. 		    var k uint32 = 2
  30.  
  31. 			factor, hasFactor := multiples[num]
  32. 			if hasFactor {
  33. 				delete(multiples, num)
  34. 				if (num + factor) % 3 == 0 {
  35. 					k = 1
  36. 				}
  37. 			} else {
  38. 				factor = num
  39. 			}
  40.  
  41. 			for newNum := num + (factor << k); ; newNum += factor << k {
  42. 				_, hasNewFactor := multiples[newNum]
  43. 				if !hasNewFactor {
  44. 					multiples[newNum] = factor
  45. 					break
  46. 				}
  47. 				k ^= 3
  48. 			}
  49.  
  50. 			if !hasFactor {
  51. 				return num
  52. 			}
  53. 		}
  54. 	}
  55.  
  56. 	return &primeGenerator
  57. }
  58.  
  59. func main() {
  60. 	n := 1000000
  61. 	primeGenerator := NewPrimeGenerator()
  62. 	for i := 1; i < n; i++ {
  63. 		primeGenerator.Next()
  64. 	}
  65. 	fmt.Printf("%d番目の素数: %d", n, primeGenerator.Next())
  66. }
Success #stdin #stdout 1.32s 47600KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1000000番目の素数: 15485863
https://ideone.com/cunq6q
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!