Merge pull request #6528 from pokgopun/pwc139

pwc139 solution in go - correct logic and improve performance on task#2

1 files changed, 46 insertions, 10 deletions

diff --git a/challenge-139/pokgopun/go/ch-2.go b/challenge-139/pokgopun/go/ch-2.go
index 84de0d6f31..2aaa6849ec 100644
--- a/challenge-139/pokgopun/go/ch-2.go
+++ b/challenge-139/pokgopun/go/ch-2.go
@@ -28,8 +28,10 @@ package main
 import (
 	"fmt"
 	"log"
+	"math"
 	"math/big"
 	"os"
+	"sort"
 	"strconv"
 	"strings"
 
@@ -55,19 +57,11 @@ func main() {
 		}
 		b.Sub(b, big.NewInt(1))
 		str := fmt.Sprintf("%0[1]*v", p-1, b.Div(b, big.NewInt(int64(p))).String())
-		l := len(str)
-		if str[:l/2] == str[l/2:l] {
-			goto skip
-		}
-		for i := 4; i <= l; i += 2 {
-			if str[:i/2] == str[i/2:i] {
-				goto skip
-			}
+		if isRepeating(str) {
+			continue
 		}
-		//fmt.Printf("%d => 0.%s\n", p, str)
 		strb.WriteString(", " + strconv.FormatUint(p, 10))
 		k--
-	skip:
 	}
 	res := strb.String()[2:]
 	fmt.Println(res)
@@ -76,3 +70,45 @@ func main() {
 		fmt.Printf("it is %t that first %d long prime(s) = %s\n", res == strings.Join(strings.Split(ans, ", ")[:n], ", "), n, res)
 	*/
 }
+
+func isRepeating(str string) bool {
+	l := uint64(len(str))
+	if l <= 1 {
+		return false
+	}
+	s := []uint64{1}
+	lim := uint64(math.Sqrt(float64(l)))
+	for i := uint64(2); i <= lim; i++ {
+		if l%i == 0 {
+			s = append(s, i)
+			if i*i != l {
+				s = append(s, l/i)
+			}
+		}
+	}
+	sort.Slice(s, func(i, j int) bool {
+		return s[i] > s[j]
+	})
+	//fmt.Println(s)
+	for _, v := range s {
+		//fmt.Println("v =", v)
+		var prev, curr string
+		var count uint64
+		for i := v; i <= l; i += v {
+			//fmt.Println("i =", i)
+			curr = str[i-v : i]
+			if curr != prev {
+				count++
+			}
+			//fmt.Println(curr, count)
+			if count > 1 {
+				//fmt.Println("!!! no repeating for", v, "chars")
+				goto skip
+			}
+			prev = curr
+		}
+		return true
+	skip:
+	}
+	return false
+}