# 3115. Maximum Prime Difference

## Description

You are given an integer array nums.

Return an integer that is the maximum distance between the indices of two (not necessarily different) prime numbers in nums.

Example 1:

Input: nums = [4,2,9,5,3]

Output: 3

Explanation: nums[1], nums[3], and nums[4] are prime. So the answer is \|4 - 1\| = 3.

Example 2:

Input: nums = [4,8,2,8]

Output: 0

Explanation: nums[2] is prime. Because there is just one prime number, the answer is \|2 - 2\| = 0.

Constraints:

• 1 <= nums.length <= 3 * 105
• 1 <= nums[i] <= 100
• The input is generated such that the number of prime numbers in the nums is at least one.

## Solutions

### Solution 1: Traversal

According to the problem description, we need to find the index $i$ of the first prime number, then find the index $j$ of the last prime number, and return $j - i$ as the answer.

Therefore, we can traverse the array from left to right to find the index $i$ of the first prime number, then traverse the array from right to left to find the index $j$ of the last prime number. The answer is $j - i$.

The time complexity is $O(n \times \sqrt{M})$, where $n$ and $M$ are the length of the array $nums$ and the maximum value in the array, respectively. The space complexity is $O(1)$.

• class Solution {
public int maximumPrimeDifference(int[] nums) {
for (int i = 0;; ++i) {
if (isPrime(nums[i])) {
for (int j = nums.length - 1;; --j) {
if (isPrime(nums[j])) {
return j - i;
}
}
}
}
}

private boolean isPrime(int x) {
if (x < 2) {
return false;
}
for (int v = 2; v * v <= x; ++v) {
if (x % v == 0) {
return false;
}
}
return true;
}
}

• class Solution {
public:
int maximumPrimeDifference(vector<int>& nums) {
for (int i = 0;; ++i) {
if (isPrime(nums[i])) {
for (int j = nums.size() - 1;; --j) {
if (isPrime(nums[j])) {
return j - i;
}
}
}
}
}

bool isPrime(int n) {
if (n < 2) {
return false;
}
for (int i = 2; i <= n / i; ++i) {
if (n % i == 0) {
return false;
}
}
return true;
}
};

• class Solution:
def maximumPrimeDifference(self, nums: List[int]) -> int:
def is_prime(x: int) -> bool:
if x < 2:
return False
return all(x % i for i in range(2, int(sqrt(x)) + 1))

for i, x in enumerate(nums):
if is_prime(x):
for j in range(len(nums) - 1, i - 1, -1):
if is_prime(nums[j]):
return j - i


• func maximumPrimeDifference(nums []int) int {
for i := 0; ; i++ {
if isPrime(nums[i]) {
for j := len(nums) - 1; ; j-- {
if isPrime(nums[j]) {
return j - i
}
}
}
}
}

func isPrime(n int) bool {
if n < 2 {
return false
}
for i := 2; i <= n/i; i++ {
if n%i == 0 {
return false
}
}
return true
}

• function maximumPrimeDifference(nums: number[]): number {
const isPrime = (x: number): boolean => {
if (x < 2) {
return false;
}
for (let i = 2; i <= x / i; i++) {
if (x % i === 0) {
return false;
}
}
return true;
};
for (let i = 0; ; ++i) {
if (isPrime(nums[i])) {
for (let j = nums.length - 1; ; --j) {
if (isPrime(nums[j])) {
return j - i;
}
}
}
}
}