Sieve of Eratosthenes
InterviewTime limit1sMemory limit256 MB
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 . The procedure is this.
- Write down every integer from to .
- Find the smallest number that is not crossed out yet and call it . is prime.
- Cross out and every multiple of that is not crossed out yet, in increasing order.
- If some number is still not crossed out, go back to step 2.
Given and , find the -th number that is crossed out.
Input
The input holds several test cases. Each line has two integers and separated by a space ().
Process every line until the end of the input.
Output
For each test case, print the -th number that is crossed out on its own line.