fork download
copy 
  1. package main
  2.  
  3. import (
  4.     "container/heap"
  5.     "fmt"
  6. )
  7.  
  8. func main() {
  9.     p := newP()
  10.     for i := 1; i < 1000000; i++ {
  11.         p()
  12.     }
  13.     fmt.Println("1,000,000th prime:", p())
  14. }
  15.  
  16. func newP() func() int {
  17.     n := 1
  18.     var pq pQueue
  19.     top := &pMult{2, 4, 0}
  20.     return func() int {
  21.         for {
  22.             n++
  23.             if n < top.pMult { // n is a new prime
  24.                 heap.Push(&pq, &pMult{prime: n, pMult: n * n})
  25.                 top = pq[0]
  26.                 return n
  27.             }
  28.             // n was next on the queue, it's a composite
  29.             for top.pMult == n {
  30.                 top.pMult += top.prime
  31.                 heap.Fix(&pq, 0)
  32.                 top = pq[0]
  33.             }
  34.         }
  35.     }
  36. }
  37.  
  38. type pMult struct {
  39.     prime int
  40.     pMult int
  41.     index int
  42. }
  43.  
  44. type pQueue []*pMult
  45.  
  46. func (q pQueue) Len() int           { return len(q) }
  47. func (q pQueue) Less(i, j int) bool { return q[i].pMult < q[j].pMult }
  48. func (q pQueue) Swap(i, j int) {
  49.     q[i], q[j] = q[j], q[i]
  50.     q[i].index = i
  51.     q[j].index = j
  52. }
  53. func (p *pQueue) Push(x interface{}) {
  54.     q := *p
  55.     e := x.(*pMult)
  56.     e.index = len(q)
  57.     *p = append(q, e)
  58. }
  59. func (p *pQueue) Pop() interface{} {
  60.     q := *p
  61.     last := len(q) - 1
  62.     e := q[last]
  63.     *p = q[:last]
  64.     return e
  65. }
Success #stdin #stdout 4.54s 56496KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1,000,000th prime: 15485863
https://ideone.com/pc4QWQ
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!