package main

import (
	"fmt"
	"math"
	"sort"
	"time"
)

func primes(n int) (answer []int) {
	bs := make([]bool, n+1)
	bs[2] = true
	for i := 3; i <= n; i += 2 {
		bs[i] = true
	}
	for i := 3; i*i <= n; i += 2 {
		for j := i; i*j <= n; j += 2 {
			bs[i*j] = false
		}
	}
	for i, ok := range bs {
		if ok {
			answer = append(answer, i)
		}
	}
	return
}

type ratio struct {
	num int
	den int
}

func (x ratio) float64() float64 {
	return float64(x.num) / float64(x.den)
}

func (x ratio) isPermutation() (answer bool) {
	a, b := x.num, x.den
	as, bs := []int{}, []int{}
	for a > 0 {
		as = append(as, a%10)
		a /= 10
	}
	for b > 0 {
		bs = append(bs, b%10)
		b /= 10
	}
	if len(as) != len(bs) {
		return
	}
	sort.Ints(as)
	sort.Ints(bs)
	for i, v := range as {
		if v != bs[i] {
			return
		}
	}
	return true
}

type rationals []ratio

func (xs rationals) max() (answer int) {
	min := math.MaxFloat64
	for _, x := range xs {
		y := x.float64()
		if y > min {
			continue
		}
		answer, min = x.num, y

	}
	return
}

func find(max int) (answer rationals, ok bool) {
	ps := primes(max)
	limit := 1e7 / ps[len(ps)-1]
	for i := 0; i < len(ps); i++ {
		if i < limit {
			continue
		}
		for j := i; j < len(ps); j++ {
			if j < limit {
				continue
			}
			n := ps[i] * ps[j]
			if n <= limit {
				continue
			}
			if n >= 1e7 {
				break
			}
			r := ratio{n, (ps[i] - 1) * (ps[j] - 1)}
			if !r.isPermutation() {
				continue
			}
			answer = append(answer, r)
			ok = true
		}
	}
	return
}

func problem70() (answer int) {
	n := int(math.Sqrt(1e7)) * 2
	for n < 1e7 {
		if res, ok := find(n); ok {
			return res.max()
		}
		n *= 2
	}
	return
}

func main() {
	start := time.Now()
	fmt.Println(problem70())
	fmt.Println(time.Now().Sub(start).Seconds())
}