Sieve of Eratosthenes

Interview

Time limit1sMemory limit128 MB

Summary

Simulate the Sieve of Eratosthenes and output which number gets crossed out on the K-th removal step.

Level: Easy3 of 10
Topics: Simulation, Math
Solved: No attempts yet

Problem

The Sieve of Eratosthenes is a classic algorithm for finding every prime number not greater than (N). In this problem, you must follow the exact order in which numbers are removed from the sieve.

The algorithm works as follows.

Write down every integer from 2 through (N).
Find the smallest number that has not been removed yet. Call it (P); this number is prime.
Remove (P), then remove every still-unremoved multiple of (P) in increasing order.
If any number remains unremoved, return to step 2.

Given (N) and (K), determine the number removed on the (K)-th removal.

Input

The first line contains two integers (N) and (K). (1 \le K < N \le 1000)

Output

Print the number that is removed on the (K)-th removal.

Examples3

Example 1
Input
```
7 3
```
Expected output
```
6
```
Example 2
Input
```
15 12
```
Expected output
```
7
```
Example 3
Input
```
10 7
```
Expected output
```
9
```