EllysIncrements | Topcoder Archive

Problem Statement

Elly has a int[] A. She may modify the array by performing a sequence of zero or more steps. In each step she may select any contiguous segment of the array and increment each element in the selected segment by one.

Elly wants to change all numbers in her array into primes. Compute and return the smallest number of steps to do that.

Definition

Class:: EllysIncrements
Method:: getMin
Parameters:: int[]
Returns:: int
Method signature:: int getMin(int[] A)
(be sure your method is public)

Notes

A prime number is a positive integer with exactly two divisors. The smallest few primes are 2, 3, 5, 7, 11, 13, 17, 19, ...

Constraints

A will contain between 1 and 100 elements, inclusive.
Each element of A will be between 1 and 1,000,000, inclusive.

Examples

```
{1, 8, 3, 3, 5, 8, 7, 2, 4}
```
```
Returns: 5
```
One optimal solution is illustrated below. 1 8 3 3 5 8 7 2 4 |--------------| 1 9 4 4 6 9 7 2 4 |-----| 1 9 4 4 6 9 7 3 5 |-----------------| 2 10 5 5 7 10 7 3 5 |--| 2 11 5 5 7 10 7 3 5 |--| 2 11 5 5 7 11 7 3 5
```
{611948,611960,611968,611984,611990,612002,612014}
```
```
Returns: 9
```
An optimal solution is to increment everything in the array nine times.
```
{1, 3, 1, 7, 1, 7, 1, 3}
```
```
Returns: 4
```
An optimal solution is to individually increment each 1 to a 2.
```
{1000000}
```
```
Returns: 3
```
Even though the initial values are only up to 10^6, Elly may be forced to increment some of the values beyond this range.

{142575, 167286, 3865, 448957, 178277, 620157, 122914, 753093, 546552, 498819}

Returns: 45

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.