COCI '08 Contest 2 #2 Reseto
View as PDFThe sieve of Eratosthenes is a famous algorithm to find all prime numbers up to . The algorithm is:
- Write down all integers between 
and
, inclusive.
 - Find the smallest number not already crossed out and call it 
;
is prime.
 - Cross out 
and all its multiples that aren't already crossed out.
 - If not all numbers have been crossed out, go to step 
.
 
Write a program that, given  and 
, find the 
 integer to be crossed out.
Input Specification
The integers  and 
 
.
Output Specification
Output the  number to be crossed out.
Sample Input 1
7 3
Sample Output 1
6
Sample Input 2
15 12
Sample Output 2
7
Sample Input 3
10 7
Sample Output 3
9
In the third example, we cross out, in order, the numbers  and 
. The seventh number is 
.
Comments