Maximum Prime Difference

Problem

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 .

Examples

Example 1

1
2
3
4
5
6
7



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

1
2
3
4
5
6
7



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 * 10^5
1 <= nums[i] <= 100
The input is generated such that the number of prime numbers in the nums is at least one.

Solution

Method 1 – Sieve and Index Scan

Intuition

We need to find the maximum distance between indices of prime numbers in the array. First, we identify which numbers are prime, then record the indices of all primes, and finally compute the difference between the maximum and minimum indices.

Approach

Use a helper function to check if a number is prime (trial division up to sqrt(n)).
Iterate through the array and collect indices where the element is prime.
If there are no primes, return 0.
Otherwise, return the difference between the maximum and minimum indices of primes.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18


class Solution {
public:
    bool isPrime(int n) {
        if (n < 2) return false;
        for (int i = 2; i * i <= n; ++i) if (n % i == 0) return false;
        return true;
    }
    int maximumPrimeDifference(vector<int>& nums) {
        int first = -1, last = -1;
        for (int i = 0; i < nums.size(); ++i) {
            if (isPrime(nums[i])) {
                if (first == -1) first = i;
                last = i;
            }
        }
        return first == -1 ? 0 : last - first;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18


func isPrime(n int) bool {
    if n < 2 { return false }
    for i := 2; i*i <= n; i++ {
        if n%i == 0 { return false }
    }
    return true
}
func maximumPrimeDifference(nums []int) int {
    first, last := -1, -1
    for i, x := range nums {
        if isPrime(x) {
            if first == -1 { first = i }
            last = i
        }
    }
    if first == -1 { return 0 }
    return last - first
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17


class Solution {
    private boolean isPrime(int n) {
        if (n < 2) return false;
        for (int i = 2; i * i <= n; ++i) if (n % i == 0) return false;
        return true;
    }
    public int maximumPrimeDifference(int[] nums) {
        int first = -1, last = -1;
        for (int i = 0; i < nums.length; ++i) {
            if (isPrime(nums[i])) {
                if (first == -1) first = i;
                last = i;
            }
        }
        return first == -1 ? 0 : last - first;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18


class Solution {
    private fun isPrime(n: Int): Boolean {
        if (n < 2) return false
        for (i in 2..Math.sqrt(n.toDouble()).toInt()) if (n % i == 0) return false
        return true
    }
    fun maximumPrimeDifference(nums: IntArray): Int {
        var first = -1
        var last = -1
        for (i in nums.indices) {
            if (isPrime(nums[i])) {
                if (first == -1) first = i
                last = i
            }
        }
        return if (first == -1) 0 else last - first
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16


class Solution:
    def is_prime(self, n: int) -> bool:
        if n < 2:
            return False
        for i in range(2, int(n ** 0.5) + 1):
            if n % i == 0:
                return False
        return True
    def maximumPrimeDifference(self, nums: list[int]) -> int:
        first = last = -1
        for i, x in enumerate(nums):
            if self.is_prime(x):
                if first == -1:
                    first = i
                last = i
        return 0 if first == -1 else last - first

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22


impl Solution {
    pub fn maximum_prime_difference(nums: Vec<i32>) -> i32 {
        fn is_prime(n: i32) -> bool {
            if n < 2 { return false; }
            let mut i = 2;
            while i * i <= n {
                if n % i == 0 { return false; }
                i += 1;
            }
            true
        }
        let mut first = -1;
        let mut last = -1;
        for (i, &x) in nums.iter().enumerate() {
            if is_prime(x) {
                if first == -1 { first = i as i32; }
                last = i as i32;
            }
        }
        if first == -1 { 0 } else { last - first }
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17


class Solution {
    isPrime(n: number): boolean {
        if (n < 2) return false;
        for (let i = 2; i * i <= n; ++i) if (n % i === 0) return false;
        return true;
    }
    maximumPrimeDifference(nums: number[]): number {
        let first = -1, last = -1;
        for (let i = 0; i < nums.length; ++i) {
            if (this.isPrime(nums[i])) {
                if (first === -1) first = i;
                last = i;
            }
        }
        return first === -1 ? 0 : last - first;
    }
}

Complexity

⏰ Time complexity: O(n * sqrt(M)), where n is the length of nums and M is the maximum value in nums (for primality check).
🧺 Space complexity: O(1), only a few variables are used.

Problem#

Examples#

Example 1#

Example 2#

Constraints#

Solution#

Method 1 – Sieve and Index Scan#

Intuition#

Approach#

Code#

Complexity#