Farthest Prime Positions

Medium

You get an integer array values that contains at least one prime number. Pick two prime elements whose positions are as far apart as possible and return that distance, the difference of their indices. You may pick the same element twice, in which case the distance is 0. A prime is greater than 1 and divisible only by 1 and itself, so 1 is not prime.

Example 1

values=[6, 7, 10, 3, 9, 11, 4] → 4

The primes sit at positions 1 (7), 3 (3) and 5 (11). The farthest apart are positions 1 and 5: 5 - 1 = 4.

Example 2

values=[1, 9, 13, 15] → 0

There is a single prime, 13 at position 2. It pairs with itself, so the distance is 0.

Example 3

values=[2, 2] → 1

Constraints

1 ≤ len(values) ≤ 3·10⁵
1 ≤ values[i] ≤ 100
At least one element is prime

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Array Math Number Theory

Similar problems

Primes Below a Bound Medium Photo Frames of the Same Shape Medium Segments on a Chart Medium Chunks With a Common Divisor Medium Segments With a Given GCD Medium

Input

values=[6, 7, 10, 3, 9, 11, 4]

Expected

Run checks the first 3 tests in your browser. Submit checks all 40 tests on the server, hidden ones included.