refactored and add tests

14 files changed, 1108 insertions, 161 deletions

diff --git a/challenge-168/pokgopun/go/ch-1.go b/challenge-168/pokgopun/go/ch-1.go
index 39b69a4633..9e2b200626 100644
--- a/challenge-168/pokgopun/go/ch-1.go
+++ b/challenge-168/pokgopun/go/ch-1.go
@@ -1,42 +1,29 @@
+/*
+The Perrin sequence is defined to start with [3, 0, 2]; after that, term N is the sum of terms N-2 and N-3. (So it continues 3, 2, 5, 5, 7, ….)
+
+A Perrin prime is a number in the Perrin sequence which is also a prime number.
+
+Calculate the first 13 Perrin Primes.
+
+f(13) = [2, 3, 5, 7, 17, 29, 277, 367, 853, 14197, 43721, 1442968193, 792606555396977]
+*/
 package main
 
 import (
 	"fmt"
-	"math/big"
+	"log"
 	"os"
-	"sort"
+
+	"github.com/pokgopun/go/perrinprime"
 )
 
 func main() {
-	l := 13
+	n := 13
 	if len(os.Args) > 1 {
-		fmt.Sscanf(os.Args[1], "%d", &l)
-	}
-	p := [3]uint{3, 0, 2}
-	pp := map[uint]struct{}{}
-	e := 0.25
-	i, n := 0, 1
-	for len(pp) < l && i < 1_000_000 {
-		i++
-		for float64(e) > 1/float64(p[0]) {
-			e *= 0.25
-			n++
-		}
-		//fmt.Printf("p0=%v,n=%v\n", p[0], n)
-		if big.NewInt(int64(p[0])).ProbablyPrime(n) {
-			pp[p[0]] = struct{}{}
+		_, err := fmt.Sscanf(os.Args[1], "%d", &n)
+		if err != nil {
+			log.Fatal(err)
 		}
-		p = [3]uint{p[1], p[2], p[0] + p[1]}
-	}
-	ppl := make([]uint, len(pp))
-	var j int
-	for k := range pp {
-		ppl[j] = k
-		j++
 	}
-	sort.SliceStable(ppl, func(i, j int) bool {
-		return ppl[i] < ppl[j]
-	})
-	fmt.Println(ppl)
-	//fmt.Println(len(pp))
+	fmt.Printf("f(%d) = [%v]\n", n, perrinprime.NewPerrinPrime(n))
 }
diff --git a/challenge-168/pokgopun/go/ch-2.go b/challenge-168/pokgopun/go/ch-2.go
index 59d4413c81..70b413fbcc 100644
--- a/challenge-168/pokgopun/go/ch-2.go
+++ b/challenge-168/pokgopun/go/ch-2.go
@@ -1,150 +1,37 @@
+/*
+You are given an integer greater than 1.
+
+Write a script to find the home prime of the given number.
+
+In number theory, the home prime HP(n) of an integer n greater than 1 is the prime number obtained by repeatedly factoring the increasing concatenation of prime factors including repetitions.
+*/
 package main
 
 import (
 	"fmt"
 	"log"
-	"math"
 	"math/big"
 	"os"
-	"strconv"
+
+	"github.com/pokgopun/go/homeprime"
 )
 
 func main() {
-	var hp homePrime
-	hp.buildPrime(5_000_000, 0)
-	//fmt.Println(hp.plist, len(hp.plist))
+	var s []*big.Int
 	if len(os.Args) > 1 {
 		for _, v := range os.Args[1:] {
-			n, err := strconv.Atoi(v)
-			if err != nil {
-				log.Fatal(err)
+			n, ok := new(big.Int).SetString(v, 10)
+			if !ok {
+				log.Fatal("failed to set string for big.int")
 			}
-			fmt.Printf("HP(%d) = %d\n", n, hp.find(n))
+			s = append(s, n)
 		}
 	} else {
-		for i := 1; i <= 47; i++ {
-			fmt.Printf("HP(%d) = %d\n", i, hp.find(i))
-		}
-	}
-}
-
-func (hp homePrime) find(n int) *big.Int {
-	bi := big.NewInt(int64(n))
-	if n == 1 {
-		return bi
-	}
-	i := 1
-	e := big.NewInt(4)
-	for e.Cmp(bi) == -1 {
-		e.Mul(e, big.NewInt(4))
-		i++
-	}
-	for !bi.ProbablyPrime(i) {
-		var str string
-		f := hp.factor(bi)
-		//fmt.Println(f)
-		for _, v := range f {
-			str += strconv.Itoa(int(v))
-		}
-		//fmt.Println(str)
-		_, ok := bi.SetString(str, 0)
-		if !ok {
-			//fmt.Println("Failed on SetString for", bi)
-			return big.NewInt(-1)
+		for i := int64(2); i <= 64; i++ {
+			s = append(s, big.NewInt(i))
 		}
 	}
-	return bi
-}
-
-func (hp *homePrime) buildPrime(n int, o int) {
-	hp.pmap = make([]bool, int(n)+1)
-	//for i := 2; i <= n; i++ {
-	for i := 1; i <= n; i++ {
-		hp.pmap[i] = true
-	}
-	if o < 1 {
-		hp.pmap[1] = false
+	for _, v := range s {
+		fmt.Printf("HP(%d) = %v\n", v, homeprime.NewHomePrime(v))
 	}
-	//for i := 2; float64(i) <= math.Sqrt(float64(n)); i++ {
-	for i := 2; float64(i) <= math.Sqrt(float64(n+o)); i++ {
-		j := i * i
-		/*
-			for j <= n {
-				hp.pmap[j] = false
-				j += i
-			}
-		*/
-		for j <= n+o {
-			if j > o {
-				hp.pmap[j-o] = false
-			}
-			j += i
-		}
-	}
-	hp.plist = []int{}
-	/*
-		for i := 2; i < len(hp.pmap); i++ {
-			if hp.pmap[i] {
-				hp.plist = append(hp.plist, i)
-			}
-		}
-	*/
-	for i := 1; i < len(hp.pmap); i++ {
-		if hp.pmap[i] {
-			hp.plist = append(hp.plist, i+o)
-		}
-	}
-}
-
-func (hp *homePrime) factor(n *big.Int) (s []int) {
-	if n.Cmp(big.NewInt(1)) == 1 {
-		j := 1
-		e := big.NewInt(4)
-		for e.Cmp(n) == -1 {
-			e.Mul(e, big.NewInt(4))
-			j++
-			//fmt.Println("In factor's e calculation => e=", e)
-		}
-		if n.ProbablyPrime(j) {
-			return []int{int(n.Int64())}
-		}
-		i := 0
-		m := new(big.Int)
-		nextPrime := big.NewInt(2)
-		if hp.plist[0] != 2 {
-			hp.buildPrime(5_000_000, 0)
-		}
-		o := 0
-		for {
-			if m.Mod(n, nextPrime).Cmp(big.NewInt(0)) != 0 {
-				i++
-				if i+1 > len(hp.plist) {
-					if o < 100_000_000_000 {
-						//hp.buildPrime(l * 1_000)
-						o += 5_000_000
-						hp.buildPrime(5_000_000, o)
-						i = 0
-					} else {
-						return []int{}
-					}
-				}
-				nextPrime = big.NewInt(int64(hp.plist[i]))
-			} else {
-				s = append(s, int(nextPrime.Int64()))
-				n.Div(n, nextPrime)
-				if n.Cmp(big.NewInt(1)) == 0 {
-					break
-				} else if n.ProbablyPrime(j) {
-					s = append(s, int(n.Int64()))
-					break
-				}
-			}
-		}
-	}
-	return s
-}
-
-type homePrime struct {
-	pmap  []bool
-	plist []int
 }
diff --git a/challenge-168/pokgopun/go/homeprime/homeprime.go b/challenge-168/pokgopun/go/homeprime/homeprime.go
new file mode 100644
index 0000000000..48f56c43c6
--- /dev/null
+++ b/challenge-168/pokgopun/go/homeprime/homeprime.go
@@ -0,0 +1,97 @@
+/*
+You are given an integer greater than 1.
+
+Write a script to find the home prime of the given number.
+
+In number theory, the home prime HP(n) of an integer n greater than 1 is the prime number obtained by repeatedly factoring the increasing concatenation of prime factors including repetitions.
+*/
+package homeprime
+
+import (
+	"log"
+	"math/big"
+
+	"github.com/jbarham/primegen"
+)
+
+type abstractPrimegen struct {
+	nextUint64 func() uint64
+	reset      func()
+}
+
+func (apg abstractPrimegen) Next() *big.Int {
+	return new(big.Int).SetUint64(apg.nextUint64())
+}
+func (apg abstractPrimegen) Reset() {
+	apg.reset()
+}
+
+type bigPrimeGenerator interface {
+	Next() *big.Int
+	Reset()
+}
+type ppFactorizer struct {
+	pg bigPrimeGenerator
+}
+
+func (ppf ppFactorizer) factor(n *big.Int) (s []*big.Int) {
+	d := new(big.Int).Set(ppf.pg.Next())
+	for {
+		if new(big.Int).Mod(n, d).Cmp(big.NewInt(0)) != 0 {
+			d.Set(ppf.pg.Next())
+		} else {
+			s = append(s, new(big.Int).Set(d))
+			n.Div(n, d)
+			if n.Cmp(big.NewInt(1)) == 0 {
+				break
+			} else if n.ProbablyPrime(0) {
+				s = append(s, n)
+				break
+			}
+		}
+	}
+	ppf.pg.Reset()
+	return s
+}
+
+type homePrime struct {
+	n, val *big.Int
+	f      interface {
+		factor(*big.Int) []*big.Int
+	}
+}
+
+func (hp homePrime) String() string {
+	return hp.val.String()
+}
+func (hp *homePrime) resolve() *homePrime {
+	if hp.n.Cmp(big.NewInt(2)) == -1 {
+		log.Fatal("input must be greater than 1")
+	} else if hp.n.Cmp(big.NewInt(49)) == 0 || hp.n.Cmp(big.NewInt(77)) == 0 {
+		hp.val = new(big.Int).SetInt64(-1)
+		return hp
+	}
+	hp.val = new(big.Int).Set(hp.n)
+	for !hp.val.ProbablyPrime(0) {
+		//hp.val.SetString(strings.ReplaceAll(hp.f.factor(hp.val), " ", ""), 10)
+		var str string
+		for _, v := range hp.f.factor(hp.val) {
+			str += v.String()
+		}
+		hp.val.SetString(str, 10)
+		//fmt.Println(hp)
+	}
+	return hp
+}
+func NewHomePrime(n *big.Int) *homePrime {
+	pg := primegen.New()
+	var apg abstractPrimegen
+	apg.nextUint64 = pg.Next
+	apg.reset = pg.Reset
+	var ppf ppFactorizer
+	ppf.pg = apg
+	var hp homePrime
+	hp.f = ppf
+	hp.n = new(big.Int).Set(n)
+	return hp.resolve()
+}
diff --git a/challenge-168/pokgopun/go/homeprime/homeprime_test.go b/challenge-168/pokgopun/go/homeprime/homeprime_test.go
new file mode 100644
index 0000000000..e0c130c962
--- /dev/null
+++ b/challenge-168/pokgopun/go/homeprime/homeprime_test.go
@@ -0,0 +1,18 @@
+package homeprime
+
+import (
+	"math/big"
+	"strings"
+	"testing"
+)
+
+const series string = "2, 3, 211, 5, 23, 7, 3331113965338635107, 311, 773, 11, 223, 13, 13367, 1129, 31636373, 17, 233, 19, 3318308475676071413, 37, 211, 23, 331319, 773, 3251, 13367, 227, 29, 547, 31, 241271, 311, 31397, 1129, 71129, 37, 373, 313, 3314192745739, 41, 379, 43, 22815088913, 3411949, 223, 47, 6161791591356884791277, -1"
+
+func TestNewHomePrime(t *testing.T) {
+	for i, ans := range strings.Split(series, ", ") {
+		res := NewHomePrime(new(big.Int).SetInt64(int64(i) + 2)).String()
+		if res != ans {
+			t.Error("incorrect result: expected " + ans + ", got " + res)
+		}
+	}
+}
diff --git a/challenge-168/pokgopun/go/perrinprime/perrinprime.go b/challenge-168/pokgopun/go/perrinprime/perrinprime.go
new file mode 100644
index 0000000000..410970b8ca
--- /dev/null
+++ b/challenge-168/pokgopun/go/perrinprime/perrinprime.go
@@ -0,0 +1,51 @@
+/*
+The Perrin sequence is defined to start with [3, 0, 2]; after that, term N is the sum of terms N-2 and N-3. (So it continues 3, 2, 5, 5, 7, ….)
+
+A Perrin prime is a number in the Perrin sequence which is also a prime number.
+
+Calculate the first 13 Perrin Primes.
+
+f(13) = [2, 3, 5, 7, 17, 29, 277, 367, 853, 14197, 43721, 1442968193, 792606555396977]
+*/
+package perrinprime
+
+import (
+	"log"
+	"math/big"
+	"sort"
+	"strconv"
+)
+
+type perrinPrime struct {
+	big.Int
+	base [3]uint
+	vals []uint
+}
+
+func NewPerrinPrime(n int) (pp perrinPrime) {
+	if n < 1 {
+		log.Fatal("must be greater than 1")
+	}
+	pp.base = [3]uint{3, 0, 2}
+	vals := map[uint]struct{}{}
+	for i := 0; i < 1_000_000 && len(vals) < n; i++ {
+		if pp.SetInt64(int64(pp.base[0])).ProbablyPrime(0) {
+			vals[pp.base[0]] = struct{}{}
+		}
+		pp.base = [3]uint{pp.base[1], pp.base[2], pp.base[0] + pp.base[1]}
+	}
+	for k := range vals {
+		pp.vals = append(pp.vals, k)
+	}
+	sort.SliceStable(pp.vals, func(i, j int) bool {
+		return pp.vals[i] < pp.vals[j]
+	})
+	return pp
+}
+func (pp perrinPrime) String() string {
+	var str string
+	for _, v := range pp.vals {
+		str += ", " + strconv.FormatUint(uint64(v), 10)
+	}
+	return str[2:]
+}
diff --git a/challenge-168/pokgopun/go/perrinprime/perrinprime_test.go b/challenge-168/pokgopun/go/perrinprime/perrinprime_test.go
new file mode 100644
index 0000000000..917b7ba9a8
--- /dev/null
+++ b/challenge-168/pokgopun/go/perrinprime/perrinprime_test.go
@@ -0,0 +1,11 @@
+package perrinprime
+
+import "testing"
+
+func TestNewPerrinPrime(t *testing.T) {
+	res := NewPerrinPrime(13).String()
+	ans := "2, 3, 5, 7, 17, 29, 277, 367, 853, 14197, 43721, 1442968193, 792606555396977"
+	if res != ans {
+		t.Error("incorrect result: expected " + ans + ", got " + res)
+	}
+}
diff --git a/challenge-168/pokgopun/go/vendor/github.com/jbarham/primegen/.gitignore b/challenge-168/pokgopun/go/vendor/github.com/jbarham/primegen/.gitignore
new file mode 100644
index 0000000000..3ee7710113
--- /dev/null
+++ b/challenge-168/pokgopun/go/vendor/github.com/jbarham/primegen/.gitignore
@@ -0,0 +1,5 @@
+_*
+6.out
+*.6
+primes
+primespeed
diff --git a/challenge-168/pokgopun/go/vendor/github.com/jbarham/primegen/LICENSE b/challenge-168/pokgopun/go/vendor/github.com/jbarham/primegen/LICENSE
new file mode 100644
index 0000000000..c4642a0d3e
--- /dev/null
+++ b/challenge-168/pokgopun/go/vendor/github.com/jbarham/primegen/LICENSE
@@ -0,0 +1,21 @@
+MIT License
+
+Copyright (c) 2020 John Barham
+
+Permission is hereby granted, free of charge, to any person obtaining a copy
+of this software and associated documentation files (the "Software"), to deal
+in the Software without restriction, including without limitation the rights
+to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
+copies of the Software, and to permit persons to whom the Software is
+furnished to do so, subject to the following conditions:
+
+The above copyright notice and this permission notice shall be included in all
+copies or substantial portions of the Software.
+
+THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
+AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
+LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
+OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
+SOFTWARE.
diff --git a/challenge-168/pokgopun/go/vendor/github.com/jbarham/primegen/README.md b/challenge-168/pokgopun/go/vendor/github.com/jbarham/primegen/README.md
new file mode 100644
index 0000000000..24e32cecb9
--- /dev/null
+++ b/challenge-168/pokgopun/go/vendor/github.com/jbarham/primegen/README.md
@@ -0,0 +1,23 @@
+# primegen
+
+*primegen* is a Go package that generates prime numbers in order using the Sieve
+of Atkin instead of the traditional Sieve of Eratosthenes.
+
+It is a relatively straightforward port of D. J. Bernstein's
+[original C implementation](http://cr.yp.to/primegen.html) but makes use of
+Go's concurrency features which should make it faster on multi-core CPUs.
+
+Do `go get github.com/jbarham/primegen` to install the package.
+
+View the package documentation online at
+https://pkg.go.dev/github.com/jbarham/primegen
+or on the command line by running `go doc github.com/jbarham/primegen`.
+
+The repository includes two additional programs that illustrate usage of the
+primegen package:
+
+1. primes, which writes prime numbers to standard out
+2. primespeed, which prints the time taken to generate the first 50,847,534
+   prime numbers
+
+John Barham, [Wombat Software](https://www.wombatsoftware.com/)
diff --git a/challenge-168/pokgopun/go/vendor/github.com/jbarham/primegen/count.go b/challenge-168/pokgopun/go/vendor/github.com/jbarham/primegen/count.go
new file mode 100644
index 0000000000..b905b06deb
--- /dev/null
+++ b/challenge-168/pokgopun/go/vendor/github.com/jbarham/primegen/count.go
@@ -0,0 +1,73 @@
+package primegen
+
+var pop = []uint32{
+	0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
+	1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
+	1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
+	2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
+	1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
+	2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
+	2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
+	3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8}
+
+// Count returns the number of prime numbers from the generator's current
+// position up to x.
+func (pg *Primegen) Count(x uint64) uint64 {
+	var count uint64 = 0
+	var smallcount, bits uint32
+
+	for {
+		for pg.num != 0 {
+			if pg.p[pg.num-1] >= x {
+				return count
+			}
+			count++
+			pg.num--
+		}
+
+		smallcount = 0
+		pos := pg.pos
+		for (pos < _B32) && (pg.base+1920 < x) {
+			for j := 0; j < 16; j++ {
+				bits = ^pg.buf[j][pos]
+				smallcount += pop[bits&255]
+				bits >>= 8
+				smallcount += pop[bits&255]
+				bits >>= 8
+				smallcount += pop[bits&255]
+				bits >>= 8
+				smallcount += pop[bits&255]
+			}
+			pg.base += 1920
+			pos++
+		}
+		pg.pos = pos
+		count += uint64(smallcount)
+
+		if pos == _B32 {
+			for pg.base+_B*60 < x {
+				pg.sieve()
+				pg._L += _B
+
+				smallcount = 0
+				for j := 0; j < 16; j++ {
+					for pos = 0; pos < _B32; pos++ {
+						bits = ^pg.buf[j][pos]
+						smallcount += pop[bits&255]
+						bits >>= 8
+						smallcount += pop[bits&255]
+						bits >>= 8
+						smallcount += pop[bits&255]
+						bits >>= 8
+						smallcount += pop[bits&255]
+					}
+				}
+				count += uint64(smallcount)
+				pg.base += _B * 60
+			}
+		}
+
+		pg.fill()
+	}
+	return count // Shouldn't get here.
+}
diff --git a/challenge-168/pokgopun/go/vendor/github.com/jbarham/primegen/fill.go b/challenge-168/pokgopun/go/vendor/github.com/jbarham/primegen/fill.go
new file mode 100644
index 0000000000..479d86b603
--- /dev/null
+++ b/challenge-168/pokgopun/go/vendor/github.com/jbarham/primegen/fill.go
@@ -0,0 +1,104 @@
+package primegen
+
+func (pg *Primegen) fill() {
+	var bits0, bits1, bits2, bits3, bits4, bits5, bits6, bits7 uint32
+	var bits8, bits9, bits10, bits11, bits12, bits13, bits14, bits15 uint32
+
+	i := pg.pos
+	if i == _B32 {
+		pg.sieve()
+		pg._L += _B
+		i = 0
+	}
+	pg.pos = i + 1
+
+	bits0 = ^pg.buf[0][i]
+	bits1 = ^pg.buf[1][i]
+	bits2 = ^pg.buf[2][i]
+	bits3 = ^pg.buf[3][i]
+	bits4 = ^pg.buf[4][i]
+	bits5 = ^pg.buf[5][i]
+	bits6 = ^pg.buf[6][i]
+	bits7 = ^pg.buf[7][i]
+	bits8 = ^pg.buf[8][i]
+	bits9 = ^pg.buf[9][i]
+	bits10 = ^pg.buf[10][i]
+	bits11 = ^pg.buf[11][i]
+	bits12 = ^pg.buf[12][i]
+	bits13 = ^pg.buf[13][i]
+	bits14 = ^pg.buf[14][i]
+	bits15 = ^pg.buf[15][i]
+
+	base := pg.base + 1920
+	pg.base = base
+
+	pg.num = 0
+
+	for mask := uint32(0x80000000); mask != 0; mask >>= 1 {
+		base -= 60
+		if bits15&mask != 0 {
+			pg.p[pg.num] = base + 59
+			pg.num++
+		}
+		if bits14&mask != 0 {
+			pg.p[pg.num] = base + 53
+			pg.num++
+		}
+		if bits13&mask != 0 {
+			pg.p[pg.num] = base + 49
+			pg.num++
+		}
+		if bits12&mask != 0 {
+			pg.p[pg.num] = base + 47
+			pg.num++
+		}
+		if bits11&mask != 0 {
+			pg.p[pg.num] = base + 43
+			pg.num++
+		}
+		if bits10&mask != 0 {
+			pg.p[pg.num] = base + 41
+			pg.num++
+		}
+		if bits9&mask != 0 {
+			pg.p[pg.num] = base + 37
+			pg.num++
+		}
+		if bits8&mask != 0 {
+			pg.p[pg.num] = base + 31
+			pg.num++
+		}
+		if bits7&mask != 0 {
+			pg.p[pg.num] = base + 29
+			pg.num++
+		}
+		if bits6&mask != 0 {
+			pg.p[pg.num] = base + 23
+			pg.num++
+		}
+		if bits5&mask != 0 {
+			pg.p[pg.num] = base + 19
+			pg.num++
+		}
+		if bits4&mask != 0 {
+			pg.p[pg.num] = base + 17
+			pg.num++
+		}
+		if bits3&mask != 0 {
+			pg.p[pg.num] = base + 13
+			pg.num++
+		}
+		if bits2&mask != 0 {
+			pg.p[pg.num] = base + 11
+			pg.num++
+		}
+		if bits1&mask != 0 {
+			pg.p[pg.num] = base + 7
+			pg.num++
+		}
+		if bits0&mask != 0 {
+			pg.p[pg.num] = base + 1
+			pg.num++
+		}
+	}
+}
diff --git a/challenge-168/pokgopun/go/vendor/github.com/jbarham/primegen/primegen.go b/challenge-168/pokgopun/go/vendor/github.com/jbarham/primegen/primegen.go
new file mode 100644
index 0000000000..0a69312525
--- /dev/null
+++ b/challenge-168/pokgopun/go/vendor/github.com/jbarham/primegen/primegen.go
@@ -0,0 +1,137 @@
+// The primegen package generates prime numbers in order.  It uses the Sieve of
+// Atkin instead of the traditional Sieve of Eratosthenes.
+//
+// The primegen Go package is a port of D. J. Bernstein's original implementation
+// in C (http://cr.yp.to/primegen.html).
+package primegen
+
+import (
+	"bufio"
+	"io"
+)
+
+const (
+	_PRIMEGEN_WORDS = 8192 // Assumes 32K L1 data cache
+	_B32            = _PRIMEGEN_WORDS
+	_B              = _PRIMEGEN_WORDS * 32
+)
+
+type Primegen struct {
+	buf  [16][]uint32
+	p    [512]uint64 /* p[num-1] ... p[0], in that order */
+	num  int
+	pos  int /* next entry to use in buf; _PRIMEGEN_WORDS to restart */
+	base uint64
+	_L   uint64
+}
+
+// New returns a new primegen.Primegen prime number generator.
+func New() *Primegen {
+	pg := new(Primegen)
+	for i := 0; i < len(pg.buf); i++ {
+		pg.buf[i] = make([]uint32, _PRIMEGEN_WORDS)
+	}
+	pg.Reset()
+	return pg
+}
+
+// Reset resets the generator at the first prime number.
+func (pg *Primegen) Reset() {
+	pg._L = 1
+	pg.base = 60
+
+	pg.pos = _PRIMEGEN_WORDS
+
+	pg.p[0] = 59
+	pg.p[1] = 53
+	pg.p[2] = 47
+	pg.p[3] = 43
+	pg.p[4] = 41
+	pg.p[5] = 37
+	pg.p[6] = 31
+	pg.p[7] = 29
+	pg.p[8] = 23
+	pg.p[9] = 19
+	pg.p[10] = 17
+	pg.p[11] = 13
+	pg.p[12] = 11
+	pg.p[13] = 7
+	pg.p[14] = 5
+	pg.p[15] = 3
+	pg.p[16] = 2
+
+	pg.num = 17
+}
+
+// Peek returns the next prime number, without advancing the generator.
+func (pg *Primegen) Peek() uint64 {
+	for pg.num == 0 {
+		pg.fill()
+	}
+
+	return pg.p[pg.num-1]
+}
+
+// Next returns the next prime number and advances the generator.
+func (pg *Primegen) Next() uint64 {
+	p := pg.Peek()
+	pg.num--
+	return p
+}
+
+// SkipTo advances the generator to generate prime numbers >= x.
+func (pg *Primegen) SkipTo(x uint64) {
+	for {
+		for pg.num != 0 {
+			if pg.p[pg.num-1] >= x {
+				return
+			}
+			pg.num--
+		}
+
+		pos := pg.pos
+		for (pos < _B32) && (pg.base+1920 < x) {
+			pg.base += 1920
+			pos++
+		}
+		pg.pos = pos
+		if pos == _B32 {
+			for pg.base+_B*60 < x {
+				pg._L += _B
+				pg.base += _B * 60
+			}
+		}
+
+		pg.fill()
+	}
+}
+
+const ndigits = 32
+
+// Write efficiently writes the list of prime numbers between low and high,
+// separated by newline, to w.
+func Write(w io.Writer, low, high uint64) (err error) {
+	var i int
+	digits := make([]byte, 32)
+	digits[ndigits-1] = '\n'
+
+	sieve := New()
+	sieve.SkipTo(low)
+	x := sieve.Next()
+	b := bufio.NewWriter(w)
+	for x < high {
+		xx := x
+		for i = ndigits - 2; i > 0; i-- {
+			digits[i] = '0' + byte(xx%10)
+			if xx < 10 {
+				break
+			}
+			xx /= 10
+		}
+		if _, err = b.Write(digits[i:]); err != nil {
+			return err
+		}
+		x = sieve.Next()
+	}
+	return b.Flush()
+}
diff --git a/challenge-168/pokgopun/go/vendor/github.com/jbarham/primegen/sieve.go b/challenge-168/pokgopun/go/vendor/github.com/jbarham/primegen/sieve.go
new file mode 100644
index 0000000000..b4973dde1f
--- /dev/null
+++ b/challenge-168/pokgopun/go/vendor/github.com/jbarham/primegen/sieve.go
@@ -0,0 +1,530 @@
+package primegen
+
+import (
+	"runtime"
+	"sync"
+)
+
+var two = [32]uint32{
+	0x00000001, 0x00000002, 0x00000004, 0x00000008,
+	0x00000010, 0x00000020, 0x00000040, 0x00000080,
+	0x00000100, 0x00000200, 0x00000400, 0x00000800,
+	0x00001000, 0x00002000, 0x00004000, 0x00008000,
+	0x00010000, 0x00020000, 0x00040000, 0x00080000,
+	0x00100000, 0x00200000, 0x00400000, 0x00800000,
+	0x01000000, 0x02000000, 0x04000000, 0x08000000,
+	0x10000000, 0x20000000, 0x40000000, 0x80000000,
+}
+
+func doit4(a []uint32, x, y int, start int64) {
+	var i, i0, y0 int
+
+	x += x
+	x += 15
+	y += 15
+
+	start += 1000000000
+	for start < 0 {
+		start += int64(x)
+		x += 30
+	}
+	start -= 1000000000
+	i = int(start)
+
+	for i < _B {
+		i += x
+		x += 30
+	}
+
+	for {
+		x -= 30
+		if x <= 15 {
+			return
+		}
+		i -= x
+
+		for i < 0 {
+			i += y
+			y += 30
+		}
+
+		i0 = i
+		y0 = y
+		for i < _B {
+			pos := uint32(i) >> 5
+			data := uint32(i) & 31
+			i += y
+			y += 30
+			bits := a[pos]
+			data = two[data]
+			bits ^= data
+			a[pos] = bits
+		}
+		i = i0
+		y = y0
+	}
+}
+
+func doit6(a []uint32, x, y int, start int64) {
+	var i, i0, y0 int
+
+	x += 5
+	y += 15
+
+	start += 1000000000
+	for start < 0 {
+		start += int64(x)
+		x += 10
+	}
+	start -= 1000000000
+	i = int(start)
+	for i < _B {
+		i += x
+		x += 10
+	}
+
+	for {
+		x -= 10
+		if x <= 5 {
+			return
+		}
+		i -= x
+
+		for i < 0 {
+			i += y
+			y += 30
+		}
+
+		i0 = i
+		y0 = y
+		for i < _B {
+			pos := uint32(i) >> 5
+			data := uint32(i) & 31
+			i += y
+			y += 30
+			bits := a[pos]
+			data = two[data]
+			bits ^= data
+			a[pos] = bits
+		}
+		i = i0
+		y = y0
+	}
+}
+
+func doit12(a []uint32, x, y int, start int64) {
+	var i, i0, y0 int
+
+	x += 5
+
+	start += 1000000000
+	for start < 0 {
+		start += int64(x)
+		x += 10
+	}
+	start -= 1000000000
+	i = int(start)
+	for i < 0 {
+		i += x
+		x += 10
+	}
+
+	y += 15
+	x += 10
+
+	for {
+		for i >= _B {
+			if x <= y {
+				return
+			}
+			i -= y
+			y += 30
+		}
+		i0 = i
+		y0 = y
+		for (i >= 0) && (y < x) {
+			pos := uint32(i) >> 5
+			data := uint32(i) & 31
+			i -= y
+			y += 30
+			bits := a[pos]
+			data = two[data]
+			bits ^= data
+			a[pos] = bits
+		}
+		i = i0
+		y = y0
+		i += x - 10
+		x += 10
+	}
+}
+
+var deltainverse = [60]int{
+	-1, _B32 * 0, -1, -1, -1, -1, -1, _B32 * 1, -1, -1, -1, _B32 * 2, -1, _B32 * 3, -1,
+	-1, -1, _B32 * 4, -1, _B32 * 5, -1, -1, -1, _B32 * 6, -1, -1, -1, -1, -1, _B32 * 7,
+	-1, _B32 * 8, -1, -1, -1, -1, -1, _B32 * 9, -1, -1, -1, _B32 * 10, -1, _B32 * 11, -1,
+	-1, -1, _B32 * 12, -1, _B32 * 13, -1, -1, -1, _B32 * 14, -1, -1, -1, -1, -1, _B32 * 15,
+}
+
+func squarefree1big(buf [16][]uint32, base uint64, q uint32, qq uint64) {
+	var i uint64
+	bound := base + 60*_B
+
+	for qq < bound {
+		if bound < 2000000000 {
+			i = qq - uint64(uint32(base)%uint32(qq))
+		} else {
+			i = qq - (base % qq)
+		}
+		if (i & 1) == 0 {
+			i += qq
+		}
+
+		if i < _B*60 {
+			pos := uint32(i)
+			n := deltainverse[pos%60]
+			if n >= 0 {
+				pos /= 60
+				idx := n + int(pos>>5)
+				buf[idx/_B32][idx%_B32] |= two[pos&31]
+			}
+		}
+
+		qq += uint64(q)
+		q += 1800
+	}
+}
+
+func squarefree1(buf [16][]uint32, L uint64, q uint32) {
+	var i uint32
+
+	base := 60 * L
+	qq := q * q
+	q = 60*q + 900
+
+	for qq < _B*60 {
+		if base < 2000000000 {
+			i = qq - (uint32(base) % qq)
+		} else {
+			i = qq - uint32(base%uint64(qq))
+		}
+		if (i & 1) == 0 {
+			i += qq
+		}
+
+		if i < _B*60 {
+			qqhigh := qq / 60
+			ilow := i % 60
+			ihigh := i / 60
+
+			qqhigh += qqhigh
+			for ihigh < _B {
+				n := deltainverse[ilow]
+				if n >= 0 {
+					idx := n + int(ihigh>>5)
+					buf[idx/_B32][idx%_B32] |= two[ihigh&31]
+				}
+
+				ilow += 2
+				ihigh += qqhigh
+				if ilow >= 60 {
+					ilow -= 60
+					ihigh += 1
+				}
+			}
+		}
+
+		qq += q
+		q += 1800
+	}
+
+	squarefree1big(buf, base, q, uint64(qq))
+}
+
+func squarefree49big(buf [16][]uint32, base uint64, q uint32, qq uint64) {
+	var i uint64
+	bound := base + 60*_B
+
+	for qq < bound {
+		if bound < 2000000000 {
+			i = qq - uint64(uint32(base)%uint32(qq))
+		} else {
+			i = qq - (base % qq)
+		}
+		if (i & 1) == 0 {
+			i += qq
+		}
+
+		if i < _B*60 {
+			pos := uint32(i)
+			n := deltainverse[pos%60]
+			if n >= 0 {
+				pos /= 60
+				idx