// oeis.org/A247665
// Russ Cox
// October 8, 2014
//
// Generate A247665 using a modified prime sieve.

package main

import (
	"bufio"
	"fmt"
	"os"
)

const Max = 100000000

var primes []int  // primes up to Max
var seq []int32   // sequence
var sieve []int32 // sieve saying which numbers can appear in the next entry; sieve[i] == 0 means i can appear

var stdout = bufio.NewWriter(os.Stdout)

func main() {
	defer stdout.Flush()

	sieve = make([]int32, Max)
	for x := 2; x < Max; x++ {
		if sieve[x] > 0 {
			continue
		}
		primes = append(primes, x)
		for y := x * 2; y < Max; y += x {
			sieve[y] = 1
		}
	}

	for i := range sieve {
		sieve[i] = 0
	}

	x := 2 // where to start looking in the sieve for the next entry
Search:
	for {
		if len(seq)%2 == 0 && len(seq) > 0 {
			factor(int(seq[len(seq)/2-1]), func(f int) {
				for g := f; g < Max; g += f {
					sieve[g]--
					if sieve[g] == 0 && g < x {
						x = g
					}
				}
			})
		}

		for ; ; x++ {
			if x >= Max {
				return
			}
			if sieve[x] == 0 {
				fmt.Fprintf(stdout, "%d %d\n", len(seq)+1, x)
				seq = append(seq, int32(x))
				factor(x, func(f int) {
					for g := f; g < Max; g += f {
						sieve[g]++
					}
				})
				sieve[x]++ // will never be 0 again
				continue Search
			}
		}
	}
}

func factor(x int, f func(int)) {
	for _, p := range primes {
		if p*p > x {
			break
		}
		if x%p == 0 {
			f(p)
			for x%p == 0 {
				x /= p
			}
		}
	}
	if x != 1 {
		f(x)
	}
}