PRIMEFACT - Editorial

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)