This page is still under construction.

Parts of this page are still being built. What you see may change.

Sieve of Eratosthenes

Interview

Time limit1sMemory limit256 MB

Summary
Simulate the sieve of Eratosthenes as described and print the K-th crossed-out number for each N and K pair.
Level

Easy2 of 10

Topics
Simulation, Implementation
Solved
No attempts yet

Problem

The sieve of Eratosthenes finds every prime that is not greater than NN. The procedure is this.

  1. Write down every integer from 22 to NN.
  2. Find the smallest number that is not crossed out yet and call it PP. PP is prime.
  3. Cross out PP and every multiple of PP that is not crossed out yet, in increasing order.
  4. If some number is still not crossed out, go back to step 2.

Given NN and KK, find the KK-th number that is crossed out.

Input

The input holds several test cases. Each line has two integers NN and KK separated by a space (2≤K<N≤10002 \le K < N \le 1000).

Process every line until the end of the input.

Output

For each test case, print the KK-th number that is crossed out on its own line.

Examples4

  1. Example 1

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

    Input
    3 2
    
    Expected output
    3
  3. Example 3

    Input
    11 2
    11 3
    11 4
    11 5
    11 6
    11 7
    11 8
    11 9
    11 10
    
    Expected output
    4
    6
    8
    10
    3
    9
    5
    7
    11
  4. Example 4

    Input
    4 2
    4 3
    5 2
    5 3
    5 4
    6 5
    
    Expected output
    4
    3
    4
    3
    5
    5