本站作为LDUOnlineJudge的测试版本进行演示,官方网站请访问http://icpc.ldu.edu.cn
[Hidden]

1342. E. Give-a-Gnocchi


Description

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, everytime 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.



The Problem:
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 kth (1-indexed) composite number that is not divisible by a prime less than n.


Input

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.

Output

Print the kth (1-indexed) composite number satisfying the given constraints.

Samples

Input Copy
10 3
Output
169

Hint

Sample Explanation:
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.

Source

UCF2019
Problem Information

Time Limit: 1000MS (C/C++,Others×2)
Memory Limit: 128MB (C/C++,Others×2)
Special Judge: No
AC/Submit: 1 / 1
Tags:
Contests involved

1038. UCF 2019
My history solutions

You didn't submit any solution!
Submit your solution

Login Register