package main

import "fmt"

var primes = []int{2, 3, 5, 7}
var primesSquared = []int{4, 9, 25, 49}

func main() {
    start, maxLength := 9, 100000

    for i := start; len(primes) < maxLength; i += 2 {
        if isPrime(i) {
            primes = append(primes, i)
            primesSquared = append(primesSquared, i*i)
        }
    }

    for _, i := range primes {
        fmt.Println(i)
    }
}

// possibleFactorsIndex returns an index in the primeSquared where
// primeSquared[index] <= n
// An index of -1 is special, meaning we actually found n in primeSquared
//
func possibleFactorsIndex(n int) int {
    // fmt.Println("looking at", n)
    low, high, mid := 0, len(primes), 0
    for high != low+1 {
        mid = (low + high) / 2
        // fmt.Println("low =", low, ", high =", high, ", mid =", mid)
        if primesSquared[mid] > n {
            high = mid
            continue
        }
        if primesSquared[mid] < n {
            low = mid
            continue
        }
        return -1
    }
    return high
}

func isPrime(n int) bool {
    topIndex := possibleFactorsIndex(n)
    if topIndex == -1 {
        return false
    }
    for i := 1; i < topIndex; i++ {
        if n%primes[i] == 0 {
            return false
        }
    }
    return true
}