Decompose Number with Prime Factor

[t im]

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).

Thanks for your help.

[lastchance]

Try 27436
(opcount is 5; route is 274326 -> 1444 -> 76 -> 4 -> 2 -> 1; count the arrows)

5 seems to be the most operations all the way up to n=100 000 000

Here's a few more with an opcount of 5:
29565 35991 50625 53757 ... 99999862

[jonnin]

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) )

[t im]

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:

using namespace std;
#include <bits/stdc++.h>

int main() {
	int n = 0;
        // first input a number indicates the number of test cases;
	cin >> n;
	vector<int> nums(n, 0);
	int maxVal = 0;
        // get n test cases;
	for (int i = 0; i < n; ++i)
	{
		cin >> nums[i];
		maxVal = max(maxVal, nums[i]);
	}
	//unordered_map<int, int> primes;
	vector<int> primes;
	primes.reserve(maxVal);
	vector<int> aux(maxVal + 1, true);
	aux[0] = false;
	aux[1] = false;
	for (int i = 2; i < maxVal; ++i)
	{
		if (aux[i])
		{	
			primes.push_back(i);
			for (int j = 2; j <= maxVal / i; ++j)
			{
				aux[i * j] = false;
			}
		}
	}
	for (int& num : nums)
	{
		vector<int> dp(num + 1, 0);
		for (int i = 2; i <= num; ++i)
		{
			if (aux[i])
			{
				dp[i] = 1;
			}
			else
			{
				dp[i] = dp[i - 1] + 1;
				auto it = upper_bound(primes.begin(), primes.end(), i);
				--it;
				do
				{
					if (i % *it == 0)
					{
						dp[i] = min(dp[i], dp[i / *it] + 1);
						break;
					}
					--it;
				} while (it != primes.begin());
			}
		}
		cout << dp[num] << endl;
	}
	return 0;
}

[Duthomhas]

@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

Equally valid:

  27436 ÷ 2  → 13718
  13718 ÷ 2  → 6859
   6859 ÷ 19 → 361
    361 ÷ 19 → 19

[lastchance]

@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.

[Duthomhas]

Oh, I misread that. (I’m bad at that, it seems.)