Senseye

Prime number palindrome Golang

Sep 28th, 2018
116
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. package main
  2.  
  3. import (
  4.     "fmt"
  5.     "math"
  6.     "time"
  7. )
  8.  
  9. // Max possible result, all 10-digits palindromes % 11 == 0
  10. const max = 999999999
  11.  
  12. type result struct {
  13.     palindrome int
  14.     left       int
  15.     right      int
  16. }
  17.  
  18. func main() {
  19.     startTime := time.Now().UnixNano()
  20.     result := findResult()
  21.     endTime := time.Now().UnixNano()
  22.  
  23.     fmt.Printf("Palindrome: %d, prime numbers %d %d, duration: %d\n", result.palindrome, result.left, result.right, endTime-startTime)
  24. }
  25.  
  26. func findResult() result {
  27.     numbers := getPrimeNumbers(10000, 99999)
  28.  
  29.     size := len(numbers)
  30.     current := result{}
  31.  
  32.     for i := 0; i < size; i++ {
  33.         for j := i + 1; j < size; j++ {
  34.             left := numbers[i]
  35.             right := numbers[j]
  36.             possible := left * right
  37.  
  38.             if possible > max {
  39.                 break
  40.             }
  41.  
  42.             if possible > current.palindrome && isPalindrome(possible) {
  43.                 current = result{possible, left, right}
  44.             }
  45.         }
  46.     }
  47.  
  48.     return current
  49. }
  50.  
  51. func getPrimeNumbers(from, to int) []int {
  52.     size := to + 1
  53.  
  54.     variants := make([]bool, size)
  55.  
  56.     for i := 0; i < size; i++ {
  57.         variants[i] = true
  58.     }
  59.  
  60.     limit := int(math.Ceil(math.Sqrt(float64(to))))
  61.  
  62.     for i := 2; i < limit; i++ {
  63.         if variants[i] {
  64.             for j := i * i; j < size; j += i {
  65.                 variants[j] = false
  66.             }
  67.         }
  68.     }
  69.  
  70.     result := make([]int, 0)
  71.     for i := from; i < size; i++ {
  72.         if variants[i] {
  73.             result = append(result, i)
  74.         }
  75.     }
  76.  
  77.     return result
  78. }
  79.  
  80. func isPalindrome(value int) bool {
  81.     digits := make([]int, 11)
  82.  
  83.     i := 0
  84.     for value > 0 {
  85.         digits[i] = value % 10
  86.         i++
  87.  
  88.         value /= 10
  89.     }
  90.  
  91.     limit := i >> 1
  92.     right := i - 1
  93.  
  94.     for j := 0; j < limit; j++ {
  95.         if digits[j] != digits[right-j] {
  96.             return false
  97.         }
  98.     }
  99.  
  100.     return true
  101. }
RAW Paste Data