No.371 I'm Not a Bad Prime
mai
🍡yurahunaProblem Statement
437: "Wobble wobble, I'm not a bad prime!"
If we try dividing 437 by 19, we get 23, confirming that it is divisible.
It seems he was not a prime number after all.
Perhaps there are other composite numbers that are being mistaken for primes.
Among the integers in the range from $L$ to $H$ inclusive, find the composite number most likely to be mistaken for a prime.
Here, the "composite number most likely to be mistaken for a prime" is defined as the composite number whose "smallest prime factor" is the largest.
For example, the smallest prime factor of $28 = 2^2 \times 7$ is 2.
Input
L H
$L$ and $H$ satisfying $(3 \le L < H \le 10^{10})$
are given separated by a space.
Note that $10^{10}$ is a value that cannot be represented by a 32-bit integer.
Output
Considering the smallest prime factor of each composite number in the range from $L$ to $H$ inclusive,
output one value for which it is the largest.
If there are multiple such values, output the one whose original integer is the largest.
Print a newline at the end.
Sample
Sample 1
Input
21 27
Output
25
Let us factorize all composite numbers from 21 to 27 into primes.
$21 = \underline{3} \times 7$
$22 = \underline{2} \times 11$
$24 = \underline{2}^3 \times 3$
$25 = \underline{5}^2$
$26 = \underline{2} \times 13$
$27 = \underline{3}^3$
The smallest prime factors are the underlined numbers.
Among the underlined numbers $3,2,5$, the largest is $5$, so we output the corresponding number, 25.
Sample 2
Input
25 35
Output
35
Let us factorize all composite numbers from 25 to 35 into primes.
$25 = \underline{5}^2$
$26 = \underline{2} \times 13$
$27 = \underline{3}^3$
$28 = \underline{2}^2 \times 7$
$30 = \underline{2} \times 3 \times 5$
$32 = \underline{2}^5$
$33 = \underline{3} \times 11$
$34 = \underline{2} \times 17$
$35 = \underline{5} \times 7$
The smallest prime factors are the underlined numbers.
Among the underlined numbers $3,2,5$, the largest is $5$, but both 25 and 35 correspond to it.
When there are multiple, we choose the largest integer. Therefore, we output 35.
Sample 3
Input
150 151
Output
150
The only composite number in the range is 150.
Sample 4
Input
56 62
Output
57
The Grothendieck prime.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。