Merge pull request #6219 from pokgopun/pwc168

pwc168 solution in go

2 files changed, 192 insertions, 0 deletions

diff --git a/challenge-168/pokgopun/go/ch-1.go b/challenge-168/pokgopun/go/ch-1.go
new file mode 100644
index 0000000000..39b69a4633
--- /dev/null
+++ b/challenge-168/pokgopun/go/ch-1.go
@@ -0,0 +1,42 @@
+package main
+
+import (
+	"fmt"
+	"math/big"
+	"os"
+	"sort"
+)
+
+func main() {
+	l := 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{}{}
+		}
+		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))
+}
diff --git a/challenge-168/pokgopun/go/ch-2.go b/challenge-168/pokgopun/go/ch-2.go
new file mode 100644
index 0000000000..59d4413c81
--- /dev/null
+++ b/challenge-168/pokgopun/go/ch-2.go
@@ -0,0 +1,150 @@
+package main
+
+import (
+	"fmt"
+	"log"
+	"math"
+	"math/big"
+	"os"
+	"strconv"
+)
+
+func main() {
+	var hp homePrime
+	hp.buildPrime(5_000_000, 0)
+	//fmt.Println(hp.plist, len(hp.plist))
+	if len(os.Args) > 1 {
+		for _, v := range os.Args[1:] {
+			n, err := strconv.Atoi(v)
+			if err != nil {
+				log.Fatal(err)
+			}
+			fmt.Printf("HP(%d) = %d\n", n, hp.find(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)
+		}
+	}
+	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 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
+}