Guest User

Untitled

a guest
Sep 28th, 2018
118
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. package main
  2.  
  3. import (
  4.     "flag"
  5.     "fmt"
  6.     "math"
  7.     "sync"
  8.     "time"
  9. )
  10.  
  11. type palindrome struct {
  12.     m1, m2, prod int
  13. }
  14.  
  15. func main() {
  16.     var primeLen int
  17.  
  18.     flag.IntVar(&primeLen, "len", 5, "length of the prime multipliers")
  19.     flag.Parse()
  20.  
  21.     t := time.Now()
  22.     fmt.Println(largestPalindrome(primeLen))
  23.     fmt.Println("Done in", time.Since(t))
  24. }
  25.  
  26. func largestPalindrome(primeLen int) palindrome {
  27.     var wg sync.WaitGroup
  28.     var best palindrome
  29.     var palindroms chan palindrome
  30.  
  31.     palindroms = make(chan palindrome)
  32.  
  33.     from, to := boundaries(primeLen)
  34.  
  35.     primes := calculatePrimes(from, to)
  36.  
  37.     cap := int(math.Pow10(2*primeLen - 1))
  38.  
  39.     for i := len(primes) - 1; i > 1; i-- {
  40.         wg.Add(1)
  41.         go findPalindromeProducts(primes, i, cap, &best, &palindroms, &wg)
  42.     }
  43.  
  44.     go closeChan(&wg, &palindroms)
  45.  
  46.     for result := range palindroms {
  47.         if result.prod > best.prod {
  48.             best = result
  49.         }
  50.     }
  51.  
  52.     return best
  53. }
  54.  
  55. func findPalindromeProducts(primes []int, i, cap int, best *palindrome, pals *chan palindrome, wg *sync.WaitGroup) {
  56.     for j := i; j > 0; j-- {
  57.         mul := primes[i] * primes[j]
  58.         if mul < cap && mul > best.prod && isPalindrome(mul) {
  59.             *pals <- palindrome{primes[i], primes[j], mul}
  60.         }
  61.     }
  62.     wg.Done()
  63. }
  64.  
  65. func calculatePrimes(from, to int) (primes []int) {
  66.     composite := make([]bool, to)
  67.  
  68.     for i := 2; i <= int(math.Sqrt(float64(to))); i++ {
  69.         for j := i * i; j < to; j += i {
  70.             composite[j] = true
  71.         }
  72.     }
  73.  
  74.     for k := from; k < to; k++ {
  75.         if !composite[k] {
  76.             primes = append(primes, k)
  77.         }
  78.     }
  79.  
  80.     return primes
  81. }
  82.  
  83. func isPalindrome(n int) bool {
  84.     order := int(math.Floor(math.Log10(float64(n))))
  85.  
  86.     for i := order / 2; i > 0; i-- {
  87.         left := (n / int(math.Pow10(order-i+1))) % 10
  88.         right := (n % int(math.Pow10(i))) / int(math.Pow10(i-1))
  89.  
  90.         if left != right {
  91.             return false
  92.         }
  93.     }
  94.  
  95.     return true
  96. }
  97.  
  98. func boundaries(l int) (int, int) {
  99.     return int(math.Pow10(l - 1)), int(math.Pow10(l) - 1)
  100. }
  101.  
  102. func closeChan(wg *sync.WaitGroup, c *chan palindrome) {
  103.     wg.Wait()
  104.     close(*c)
  105. }
RAW Paste Data