25862번 - Give-a-Gnocchi 다국어

Your favorite Italian restaurant is having a promotion. The restaurant is giving away “free” gnocchi soups. The only cost is to provide them with a prime number. But the restaurant does not want to go out of business; they will only accept a prime number if it is not already in their database. Once a prime number is accepted, they add it to their database. As it turns out, every time you have tried to give them a prime number, no matter how large, they already have it in their database, so you end up having to pay for your meal.

Your friend, Euler, noticed something odd about the verification program. Euler gave the restaurant the number 24,990,001, and they accepted it. Euler realized this value was not prime after he checked it at home, so he did some analysis to determine what happened. It turns out the restaurant’s database accepts any number (even a composite number!) that is not divisible by a prime lower than or equal to some value n; which means you can easily get your gnocchi soup (albeit a little dishonestly) by finding a number (even a composite) the restaurant will accept. Basically, on the first day, you could give the first composite number that is not divisible by a prime lower than or equal to n; on the second day, you would give the next composite number that is not divisible by a prime lower than or equal to n, etc.

Since the restaurant keeps track of the numbers given to them, it is difficult to find what number to give to the restaurant next. Your other friend, Fermat, suggests that you write a program that will take in a value n and a day k, and it will output the k^th (1-indexed) composite number that is not divisible by a prime less than n.

The input consists of a single line providing two positive integers: n (n ≤ 1000), representing the highest possible value for checking for primality, and k (k ≤ 1000), indicating the index of the desired composite number.

Print the k^th (1-indexed) composite number satisfying the given constraints.

In the first sample case, the smallest composite numbers not divisible by a value less than or equal to 10 are 121, 132, 169, 189, 221. On the first day we could give 121. The second day we would use 132. On the third day (when k = 3) we would use 169.

For the second sample case, the answer is 4, since it is both the 1st composite number and the first number not divisible by any prime less than or equal to 1.

For the last case, the smallest composite numbers not divisible by a prime less than or equal to 19 include 529, 667, 713, 841, 851, 899, 943, 961, and 989. The 7th value in the list is 943, which will be the value given on the 7th day