407223: GYM102697 194 RSA Cipher

The RSA cipher, invented in 1977, is widely used today for encryption of data online. The first step of making a key for the RSA cipher is choosing a number $$$n$$$ at the start. In the real world, $$$n$$$ is extremely large, usually at least 50 digits long, but for this problem, you'll select an $$$n$$$ less than $$$10^6$$$.

When choosing the numbers for the key, $$$n$$$ must be a semiprime. A semiprime is any number that has exactly two prime factors, not necessarily distinct. For example, 6, 34, and 25 are semiprimes, but 30, 7, and 27 are not semiprimes.

After choosing $$$n$$$, you choose another number $$$e$$$, which can be any number less than $$$n$$$ and greater than one that is relatively prime to $$$n$$$. Two numbers are relatively prime if they don't share any prime factors.

$$$n$$$ and $$$e$$$ compose the "public key", and the private key is calculated differently, which won't be covered in this problem.

Given a number $$$m$$$, find the public key that has the largest $$$n$$$, where $$$n$$$ and $$$e$$$ are less than or equal to $$$m$$$. If multiple answers have the same $$$n$$$, pick the one with the smallest $$$e$$$.

The only line of input contains a single positive integer $$$m$$$: the upper limit on $$$n$$$ and $$$e$$$.

Output two space-separated integers, representing your chosen public key: $$$n$$$ and $$$e$$$, as described above. $$$n$$$ and $$$e$$$ should both be less than or equal $$$m$$$, $$$n$$$ should be a semiprime, and $$$e$$$ should be relatively prime to $$$n$$$.

197

194 3

259

259 2

372

371 2

98276

98267 2