No.3127 Multiple of Twin Prime
タグ : / 解いたユーザー数 130
作問者 : 👑
Iroha_3856
nikoro256
Problem Statement
When both $p, p + 2$ are prime, the pair is called twin primes.
We define an integer $n$ that can be expressed as $n = p \times (p + 2)$ using a prime $p$ and a prime $p + 2$ as a "product of twin primes".
You are given an integer $N$. Find the largest "product of twin primes" that is at most $N$.
However, if there is no "product of twin primes" at most $N$, output -1.
You are given $T$ test cases; answer each of them.
Constraints
- $1 \leq T \leq 10^5$
- $1 \leq N \leq 10^{14}$
- All input values are integers
Input
The input is given from standard input in the following format. Here, $\mathrm{case}_i ~ (i = 1, 2, \cdots, T)$ is the $i$-th test case.
$T$
$\mathrm{case}_1$
$\mathrm{case}_2$
$\vdots$
$\mathrm{case}_T$
Each test case is given in the following format.
$N$
Output
Output $T$ lines. On the $i$-th line, output the answer to the $i$-th test case.
For each test case, output the largest "product of twin primes" that is at most $N$. However, if there is no "product of twin primes" at most $N$, output -1.
Sample
Sample
Input
6 16 5 143 425 998244353 100000000000000
Output
15 -1 143 323 994897763 99999440000783
The following holds for the $1$-st through $3$-rd test cases.
- For the $1$-st test case, the largest "product of twin primes" at most $16$ is $15 = 3 \times 5$.
- For the $2$-nd test case, there is no "product of twin primes" at most $5$.
- For the $3$-rd test case, the largest "product of twin primes" at most $143$ is $143 = 11 \times 13$.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。