Given a number n, Here are two operations can be taken:
* n - 1
* n divide by its prime factor
Question: In order to decompose n to 1, what is the minimal operations should be taken?
For example, in term of number 29, it is a prime number. So, the number of operation is 1. For number 30, the number of operations is 2(30 minus 1 and it is a prime number).
PS: It seems that we can decompose a number in no more than 4 operations(Not sure).
What help are you asking for? Do you have a max val for N? Do you have a strategy to factor a number into its prime factors? I recommend you build a lookup table of the prime numbers up to sqrt of your biggest N, for a starting point. (via the sieve, so this is likely a vector<bool> isprime(sqrt(N) +1) )
Thanks for all the reply first.
I meet with the problem in a coding exam. I seek for a solution can solve the problem with less time.
Here is my code which turns to time limit exceeded:
@lastchance
OP’s assignment specifically asks for minimal number of operations. Just by eyeball that 4 -> 2 -> 1 could have been 4 -> 3, which is prime, so 4 operations.
27436 ÷ 19 → 1444
1444 ÷ 19 → 76
76 ÷ 19 → 4
4 - 1 → 3
@Duthomas, he's asking how to decompose to 1, not just to a prime number. You are one operation short (the last divide by a prime number).
Look at his examples.
29->1 (1 operation)
30 -> 29 -> 1 (2 operations)
Count the arrows (paths), not the nodes.
I stand by my answer. FWIW, I worked BACKWARDS from 1 to get the results - a sort of shortest-path calculation. And yes, I precomputed the primes (with a sieve).
Of course, there may be many different routes from a number with the same opcount. For example, here is another one of length 5 (yes!) from 27436. This one makes use of the "subtract 1" operation, rather than successively dividing by 5 prime factors:
27436 -> 27435 -> 465 ->15 -> 3 -> 1
... but it's still of length 5 (optimal for this number).
5 seems to survive as the "maximum optimum" up to all the values of n that I can safely and efficiently compute. Whether it is true in general I don't know: there must be a theorem out there, but I haven't located it. The number 5 makes it look awfully Galois-like, but it may be just a fluke.