import scala.math._

object Main extends App {
    var limit = 1500000;
    var sqrtLimit = sqrt(limit.toDouble).toInt

    var isPrime = new Array[Boolean](1500001)
    isPrime(2) = true
    isPrime(3) = true

    var n = 0

    var x2 = 0
    var y2 = 0

    for (i <- 1 to sqrtLimit) {
        x2 += 2 * i - 1
        y2 = 0

        for (j <- 1 to sqrtLimit) {
            y2 += 2 * j - 1

            n = 4 * x2 + y2
            if ((n <= limit) && (n % 12 == 1 || n % 12 == 5)) {
                isPrime(n) = !isPrime(n)
            }

            n -= x2
            if ((n <= limit) && (n % 12 == 7)) {
                isPrime(n) = !isPrime(n)
            }

            n -= 2 * y2
            if ((i > j) && (n <= limit) && (n % 12 == 11)) {
                isPrime(n) = !isPrime(n)
            }
        }
    }

    for (i <- 5 to sqrtLimit) {
        if (isPrime(i)) {
            n = i * i
            for (j <- n to limit by n) {
                isPrime(j) = false
            }
        }
    }

    println(show())

    def show(): Int = {
        var current = 3
        var prime = 5

        for (i <- 6 to limit) {
            if (current == 10001) {
                return prime
            }
            if (isPrime(i) && i % 3 != 0 && i % 5 != 0) {
                current += 1
                prime = i
            }
        }

        return prime
    }
}