package main import ( "fmt" "math/big" "os" ) type UnionFind struct { n int ig []int gi [][]int } func MakeUF(n int) *UnionFind { uf := new(UnionFind) uf.n = n uf.ig = make([]int, n) uf.gi = make([][]int, n) for i := 0; i < n; i++ { uf.ig[i] = i uf.gi[i] = []int{i} } return uf } func (uf *UnionFind) merge(a, b int) { a = uf.ig[a] b = uf.ig[b] if a == b { return } if len(uf.gi[a]) < len(uf.gi[b]) { tmp := a a = b b = tmp } for _, c := range uf.gi[b] { uf.ig[c] = a } uf.gi[a] = append(uf.gi[a], uf.gi[b]...) } func (uf *UnionFind) same(a, b int) bool { return uf.ig[a] == uf.ig[b] } const PS = 50000 var pr [PS]bool func init() { for i := 2; i < PS; i++ { pr[i] = true } for i := 2; i < PS; i++ { if pr[i] == false { continue } for j := 2 * i; j < PS; j += i { pr[j] = false } } } func solve1(n int) int { for i := 2; i <= n; i++ { uf := MakeUF(n + 1) for j := 1; j <= n; j++ { if j%i != 1 { if !pr[j] && !pr[j-1] { uf.merge(j, j-1) } } if i < j { if !pr[j] && !pr[j-i] { uf.merge(j, j-i) } } } if uf.same(1, n) { return i } } os.Exit(1) return -1 } func solve2(n *big.Int) int { for i := 2; i < 1000; i++ { const B = 9000 { uf := MakeUF(B + 1) for j := 1; j <= B; j++ { if j%i != 1 { if !pr[j] && !pr[j-1] { uf.merge(j, j-1) } } if i < j { if !pr[j] && !pr[j-i] { uf.merge(j, j-i) } } } if !uf.same(1, B/i*i) { continue } } { uf := MakeUF(B + 1) ii := big.NewInt(int64(i)) bpr := make([]bool, B+1) for jj := 0; jj <= B; jj++ { j := n j.Sub(j, big.NewInt(int64(B-jj))) bpr[jj] = j.ProbablyPrime(100) } for jj := 0; jj <= B; jj++ { j := n j.Sub(j, big.NewInt(int64(B-jj))) if k := j; jj > 0 && k.Mod(k, ii).Cmp(big.NewInt(1)) != 0 { if !bpr[jj] && !bpr[jj-1] { uf.merge(jj, jj-1) } } if i <= jj { if !bpr[jj] && !bpr[jj-1] { uf.merge(jj, jj-i) } } } if nn := n; uf.same(B-int(nn.Mod(nn, big.NewInt(int64(i))).Int64()), B) { return i } } } os.Exit(1) return -1 } func main() { b := new(big.Int) fmt.Scan(b) if b.Cmp(big.NewInt(20000)) == -1 { fmt.Println(solve1(int(b.Int64()))) } else { fmt.Println(solve2(b)) } }