### Decompose Number with Prime Factor

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

Last edited on
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
Last edited on
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) )
Last edited on
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:
 ``12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061`` ``````using namespace std; #include int main() { int n = 0; // first input a number indicates the number of test cases; cin >> n; vector 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 primes; vector primes; primes.reserve(maxVal); vector 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 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; }``````
Last edited on
@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
@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.
Last edited on