{"problem":{"name":"194. RSA Cipher","description":{"content":"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","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":1000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF10269194"},"statements":[{"statement_type":"Markdown","content":"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$.\n\nWhen 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.\n\nAfter 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\n$n$ and $e$ compose the \"public key\", and the private key is calculated differently, which won't be covered in this problem.\n\nGiven 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$.\n\nThe only line of input contains a single positive integer $m$: the upper limit on $n$ and $e$.\n\nOutput 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$.\n\n## Input\n\nThe only line of input contains a single positive integer $m$: the upper limit on $n$ and $e$.\n\n## Output\n\nOutput 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$.\n\n[samples]","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ m \\in \\mathbb{Z}^+ $ be the upper bound.  \nLet $ \\mathcal{S} = \\{ n \\in \\mathbb{Z} \\mid 1 < n \\leq m,\\ n \\text{ is a semiprime} \\} $.  \nFor each $ n \\in \\mathcal{S} $, let $ \\mathcal{E}_n = \\{ e \\in \\mathbb{Z} \\mid 1 < e \\leq m,\\ \\gcd(e, n) = 1 \\} $.\n\n**Constraints**  \n1. $ 1 < n \\leq m $  \n2. $ n $ is a semiprime (product of exactly two primes, not necessarily distinct)  \n3. $ 1 < e \\leq m $  \n4. $ \\gcd(e, n) = 1 $\n\n**Objective**  \nFind $ (n^*, e^*) $ such that:  \n- $ n^* = \\max \\mathcal{S} $,  \n- $ e^* = \\min \\mathcal{E}_{n^*} $.\n\nOutput: $ n^* $ and $ e^* $.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF10269194","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}