3115. Maximum Prime Difference

Problem Link

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.

Solution

---

Python3

def generate_primes(n):
	isPrime = [True] * (n + 1)
	isPrime[0] = isPrime[1] = False
 
	for i in range(2, n + 1):
		if isPrime[i]:
			for j in range(i * i, n + 1, i):
				isPrime[j] = False
 
	return isPrime
 
PRIMES = generate_primes(105)
 
class Solution:
    def maximumPrimeDifference(self, nums: List[int]) -> int:
        N = len(nums)
        first = last = -1
        
        for i, x in enumerate(nums):
            if PRIMES[x]:
                if first == -1:
                    first = i
                    last = i
                else:
                    last = i
        
        return last - first