Description:
You have a number $$$n$$$, and the smallest prime factor of $$$n$$$ is $$$p$$$. Turning $$$n$$$ into $$$\frac{n+p}{2}$$$ is called an operation.
You should do this until $$$n$$$ is prime.
Find the number of times the operation can be performed.
No limits.Could you find the lowest complexity of this problem?It's unnecessary to consider the complexity of input and output.
the problem here reduces to quicly finding the smallest prime factor , as the halfing operation will take at most logn steps before n becomes 1 .
for small n , say up to 10^7 you can precalculate the smallest prime factor (spf) array by sieving , so you will get the spf of n in O(1) after O(nloglogn) precalc , so the total complexity will be O(nloglogn) .
if n is bigger but its square root is still small , (<=10^13) you can precalulate primes up to sqrt(n) , and at each step just go through them , if you dont find any divisor , it means n itself is a prime , and total TC will be <=O(sqrt(n)*logn) (you can calculate it exactly as an exercise ) .
for biggere n , I think it might be doable some pollard rho or richard mill tricks , but I dont have much knowledge in them so am not sure .
I don't think the operation converges to 1. Consider the following example:
n = 21 => p = 3. After the operation, it becomes n = (21 + 3) / 2 = 12.
n = 12 => p = 2. After the operation, it becomes n = (12 + 2) / 2 = 7.
In addition, if n is prime then p = n, and the operation becomes (n + n) / 2, meaning that we can't further get any different result from a prime n.
Therefore, although n = 21, whose spf is 3, the final result is 7, which doesn't fit your algorithm.
It either reaches 1 or a prime , in your example once you reached 7 you were done
Sorry, I misunderstood your statement in the first sentence and didn't read the rest thoroughly.
I also agree on the methods that you mentioned, and the simplest would be to use sieve to precalculate for small $$$n$$$. However, since we are optimizing for the smallest time complexity, I guess the best algorithm would be Pollard's Rho. Though, it would take some more effort and time to implement it and optimize it.
Still, I want to point out to one little matter.
I've thought about it for some time and reached the conclusion that it never reaches $$$1$$$ assuming that $$$n \gt = 2$$$. Otherwise there would be no SPF.
Because it's always a composite number that we can apply the operation on, it can never become $$$1$$$ since the result is either a composite or a prime.
Proof. For $$$\dfrac{n + p}{2}$$$ to be one, $$${n + p} = {2}$$$ must hold. However, since $$$n \gt = 2$$$ it can never become 1.
I know it's a silly topic, but I just wanted to put it on the shelf.
If $$$p \lt n$$$ (because $$$n$$$ is supposed to be composite), then $$$p \le \sqrt{n}$$$, because if it were to be greater, then $$$\frac{n}{p}$$$ would be a contradiction. So $$$n$$$ turns into at most $$$\frac{n + \sqrt{n}}{2}$$$ which should be $$$\log_{2-\epsilon}$$$ (I'm too lazy to prove if it is actually $$$\log_2$$$)
For each odd result we get, we need to apply minimum $$${1 + {\lfloor\log{2}{n}\rfloor}}$$$, more operations. So I assume it would be somewhat larger than $$$\lfloor\log{2}{n}\rfloor$$$ as you said.
you can use pollard's rho to find spf in $$$O(n ^ {1/4} log_2 n)$$$ to get an algorithm runs in $$$O(n ^ {1/4} log_2^2 n)$$$
Number of steps never exceeds log2 N. complexity is O(sqrt(n)) with naive trial divison if only one test case, O(n log logn) if you can have multiole tests. Elliptic Curve Method does it on e^sqrt(2 ln p ln ln p) * log² n. due to p being small its tiny