# PRIMEFACT - Editorial

Author: abhi_inav
Testers: tabr, iceknight1093
Editorialist: iceknight1093

TBD

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)