#P6421. Kth Removed Number in the Sieve of Eratosthenes

    ID: 19636 Type: Default 1000ms 256MiB

Kth Removed Number in the Sieve of Eratosthenes

Kth Removed Number in the Sieve of Eratosthenes

The Sieve of Eratosthenes is a famous algorithm to find all the prime numbers up to \( n \). The algorithm works as follows:

  1. Write down all the integers between 2 and \( n \) (inclusive).
  2. Find the smallest number that has not been removed and call it \( p \); \( p \) is a prime.
  3. Remove \( p \) and all its multiples that have not been removed.
  4. If there are still numbers remaining, repeat from step 2.

Given two integers \( n \) and \( k \), your task is to determine the kth number that is removed during this process.

inputFormat

The input consists of a single line containing two integers \( n \) and \( k \) separated by a space.

\( 2 \leq n \leq 10000 \) and \( k \) is such that the kth removed number exists.

outputFormat

Output the kth number that is removed during the sieve process.

sample

7 3
6