PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: abhi_inav
Testers: tabr, iceknight1093
Editorialist: iceknight1093
DIFFICULTY:
TBD
PREREQUISITES:
None
PROBLEM:
You start with an integer X. In one move, you add to X its smallest prime factor.
How many moves till your integer is at least Y?
EXPLANATION:
If X is even, its smallest prime factor is 2; and X+2 is also even so this will continue to be the case from here on.
Since we’re adding exactly 2 at each step, the number of steps needed to reach Y is quite easy to calculate:
- Let d = Y-X be the distance between X and Y.
- Each step shortens this distance by 2, so we need \displaystyle \left\lceil \frac{d}{2} \right\rceil steps, where \left\lceil \ \right\rceil denotes the ceiling function.
This can be computed in \mathcal{O}(1).
If X is odd, then its smallest prime factor is an odd number.
However, on adding this odd number to X, the resulting number is even!
So, we have the following solution:
- If X is even, solve directly in \mathcal{O}(1)
- If X is odd, perform the first move manually. Now X is even, so again it can be solved for in $\mathcal{O}(1).
TIME COMPLEXITY
\mathcal{O}(1) per test case.
CODE:
Editorialist's code (Python)
for _ in range(int(input())):
x, y = map(int, input().split())
ans = 0
if x%2 == 1:
ans = 1
for i in range(2, x+1):
if x%i == 0: # smallest non-1 factor is also smallest prime factor
x += i
break
print(ans + (y-x+1)//2)