import scala.io.StdIn.readLine

object Main {
  def main(args: Array[String]): Unit ={
    D.answer()
  }
}

object D{
  import scala.math

  def multi(a:Long, b:Long):Long = a * b

  def primes(max:Int): List[Int] = {
    (1 to (max / 6).toInt + 1).foldLeft(List(2,3)){(acc,c) => {
      val a = c*6-1
      val b = c*6+1
//      val sq = acc.takeWhile(a=> a <= math.sqrt(b).toInt)
      val sq = acc
      val k=if(sq.foldLeft(true){(acc, c) => if(acc && a % c != 0) true else false}) List(a) else List()
      val v=if(sq.foldLeft(true){(acc, c) => if(acc && b % c != 0) true else false}) List(b) else List()
      acc++k++v
    }}
  }
  def multiper(n:Int, m:Int):(Int, Int) = if(m % n == 0) (1 + multiper(n,m/n)._1, multiper(n,m/n)._2) else (0, m)

  def fac(l:List[Int], m:Int): List[Int] = {
    l match {
      case List() => {
        println(m)
        List()
      }
      case x => multiper(l.head, m) match {
        case (0,1) => List()
        case (x,1) => List(x)
        case (0,y) => fac(l.tail, y)
        case (x,y) => List(x) ::: fac(l.tail, y)
      }
    }
  }

  def invmod(p:Long, g:Long) = {
    def euclidean(px:Long, py:Long, pgcd: Long, x:Long, y:Long, gcd: Long):Long = {
      pgcd % gcd match {
        case 0 => (x + g) % g
        case m => {
          val d = pgcd / gcd
          euclidean(x,y,gcd, px-(d*x), py-(d*y), m)
        }
      }
    }
    euclidean(1,0,p,0,1,g)
  }

  def comb(n:Int, k:Int, p:Int):Long = {
    (1 to k).foldLeft(1.toLong)((acc,c)=> (multi((multi(acc,(n-c+1)) % p), invmod(c,p))) % p)
  }

  def input[A](change: String => A) = readLine.split(" ").map(change(_))
  def answer(): Unit ={
    println(primes(100))
    println(primes(31627))

//    val p = math.pow(10,9).toInt + 7
//    val a = input((a=>a.toInt))
//    val n = a(0)
//    val m = a(1)
//    val f = fac(primes(math.sqrt(p).toInt), m)
//    val ans = f.foldLeft(1.toLong)((acc,c)=>(multi(acc, comb(c+n-1, c, p))) % p)
//    println(ans)

  }
}