### 2013 Canadian Computing Competition, Stage 1

## Problem S5: Factor Solitare

In the game of Factor Solitaire, you start with the number 1, and try to
change it to some given target number `n` by repeatedly using the
following operation. In each step, if `c` is your current number, you
split it into two positive factors `a`, `b` of your
choice such that
`c` = `a` * `b`. You then add
`a` to your current number `c` to get your new current
number. Doing this costs you `b` points. You continue doing this
until your current number is `n`, and you try to achieve this at the
cost of a minimum total number of points.

For example, here is one way to get to 15:

- start with 1
- change 1 to 1+1=2—cost so far is 1
- change 2 to 2+1=3—cost so far is 1+2
- change 3 to 3+3=6—cost so far is 1+2+1
- change 6 to 6+6=12—cost so far is 1+2+1+1
- change 12 to 12+3=15—cost so far is 1+2+1+1+4=9.

In fact, this is the minimum possible total cost to get 15. You want to compute the minimum total cost for other target end numbers.

### Input

The input costs of a single integer `N` ≥ 1. In at
least half of the cases `N` ≤ 5×10^{4}, in
at least another quarter of the cases
`N` ≤ 5×10^{5}, and in the remaining cases
`N` ≤ 5×10^{6}.

### Output

Compute the minimum cost that gets you to `N`.

### Sample Input 1

15

### Sample Output 1

9

### Sample Input 2

2013

### Sample Output 2

91

### Explanation for Sample Case 2

For example, start with 1, then get to 2, 4, 5, 10, 15, 30, 60, 61, 122, 244, 305, 610, 671, 1342, and then 2013.

All Submissions

Best Solutions

**Point Value:** 15 (partial)

**Time Limit:** 3.00s

**Memory Limit:** 256M

**Added:** May 19, 2013

**Languages Allowed:**

C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

## Comments (Search)

It's quiet in here...