# UVa 10871

## Summary

Use an ${\displaystyle O(n^{2})}$ algorithm with a sieve.

## Explanation

First, we reduce the problem of finding the sum between two indices to ${\displaystyle O(1)}$ by linearly summing the elements - ${\displaystyle sum(n)=sum(n-1)+element(n)}$. We can then find the sum between two indices by simply taking the difference - ${\displaystyle sum(i,j)=sum(j)-sum(i)}$. Try out all possibilities of ${\displaystyle i}$ and ${\displaystyle j}$, cohering to the problem specs, and it should run within reasonable time.

## Notes

• The worst case for the input is not as bad as the problem actually denotes.

## Input

```3
5 3 5 6 3 8
5 6 4 5 4 12
21 15 17 16 32 28 22 26 30 34 29 31 20 24 18 33 35 25 27 23 19 21
```

## Output

```Shortest primed subsequence is length 2: 5 6
Shortest primed subsequence is length 3: 4 5 4
This sequence is anti-primed.
```