PrimeMaker | Topcoder Archive

Problem Statement

You are given a positive int n. You can perform two types of operations:

Change any single digit into any other digit.
Remove any single digit.

Return the minimum number of operations required to change n into a prime number.

Definition

Class:: PrimeMaker
Method:: minimalOperation
Parameters:: int
Returns:: int
Method signature:: int minimalOperation(int n)
(be sure your method is public)

Notes

A prime number is a positive integer with exactly two divisors: 1 and the number itself. The first few prime numbers are 2, 3, 5, 7, 11, 13, ...
When replacing a digit, you are not allowed to create a leading zero. Note that instead of doing that you can simply remove the leading digit, which has the same effect.

Constraints

n will be between 1 and 106, inclusive.

Examples

```
26
```
```
Returns: 1
```
We could remove the 6, leaving 2 which is prime. Alternately, we could change the 6 to get 23 or 29. Either way it takes one operation.
```
47
```
```
Returns: 0
```
This is already a prime number.
```
222222
```
```
Returns: 2
```
Sometimes, one change is not enough. One optimal solution is to change the number into 272227. Another optimal solution is to erase one of the digits and then change the last digit into a 9.
```
1
```
```
Returns: 1
```
The number 1 is not a prime number.

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.