#P6421. Kth Removed Number in the Sieve of Eratosthenes
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:
- Write down all the integers between 2 and \( n \) (inclusive).
- Find the smallest number that has not been removed and call it \( p \); \( p \) is a prime.
- Remove \( p \) and all its multiples that have not been removed.
- 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