<p>You are given an integer array <code>nums</code>.</p>

<p>Return an integer that is the <strong>maximum</strong> distance between the <strong>indices</strong> of two (not necessarily different) prime numbers in <code>nums</code><em>.</em></p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<div class="example-block">
<p><strong>Input:</strong> <span class="example-io">nums = [4,2,9,5,3]</span></p>

<p><strong>Output:</strong> <span class="example-io">3</span></p>

<p><strong>Explanation:</strong> <code>nums[1]</code>, <code>nums[3]</code>, and <code>nums[4]</code> are prime. So the answer is <code>|4 - 1| = 3</code>.</p>
</div>

<p><strong class="example">Example 2:</strong></p>

<div class="example-block">
<p><strong>Input:</strong> <span class="example-io">nums = [4,8,2,8]</span></p>

<p><strong>Output:</strong> <span class="example-io">0</span></p>

<p><strong>Explanation:</strong> <code>nums[2]</code> is prime. Because there is just one prime number, the answer is <code>|2 - 2| = 0</code>.</p>
</div>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= nums.length &lt;= 3 * 10<sup>5</sup></code></li>
	<li><code>1 &lt;= nums[i] &lt;= 100</code></li>
	<li>The input is generated such that the number of prime numbers in the <code>nums</code> is at least one.</li>
</ul>

from typing import List

class Solution:
    def maximumPrimeDifference(self, nums: List[int]) -> int:
        if not nums:
            return 0
        
        size = max(nums)
        if size < 2:
            return 0
        
        # 에라토스테네스의 체 초기화
        primes = [True] * (size + 1)
        primes[0] = primes[1] = False  # 0과 1은 소수가 아님

        # 에라토스테네스의 체 최적화: i의 제곱부터 시작하여 배수를 제거
        for i in range(2, int(size**0.5) + 1):
            if primes[i]:
                primes[i*i:size+1:i] = [False] * len(range(i*i, size+1, i))
        
        first_prime_idx = -1
        last_prime_idx = -1

        # nums를 순회하며 첫 번째와 마지막 소수의 인덱스를 찾음
        for idx, num in enumerate(nums):
            if num >= 2 and primes[num]:
                if first_prime_idx == -1:
                    first_prime_idx = idx
                last_prime_idx = idx
        
        # 소수가 두 개 이상 존재할 때 인덱스 차이 반환, 그렇지 않으면 0 반환
        if first_prime_idx != -1 and last_prime_idx != -1 and first_prime_idx != last_prime_idx:
            return last_prime_idx - first_prime_idx
        else:
            return 0
740