2716. Prime Subtraction Operation

class Solution:
    def primeSubOperation(self, nums: List[int]) -> bool:
        # Generate primes up to 1000 using Sieve of Eratosthenes
        # Time: O(n * sqrt(max_num)), Space: O(max_num)
        
        max_val = 1001
        is_prime = [True] * max_val
        is_prime[0] = is_prime[1] = False
        
        for i in range(2, int(max_val**0.5) + 1):
            if is_prime[i]:
                for j in range(i*i, max_val, i):
                    is_prime[j] = False
        
        # Get list of primes
        primes = [i for i in range(2, max_val) if is_prime[i]]
        
        # Binary search for largest prime less than target
        def get_largest_prime_less_than(target):
            left, right = 0, len(primes) - 1
            result = -1
            while left <= right:
                mid = (left + right) // 2
                if primes[mid] < target:
                    result = primes[mid]
                    left = mid + 1
                else:
                    right = mid - 1
            return result
        
        prev = 0  # Previous element (should be strictly less than current)
        
        for num in nums:
            # We need: num - prime > prev, i.e., prime < num - prev
            # Find largest prime < (num - prev)
            if num <= prev:
                return False
            
            # Find largest prime we can subtract such that num - prime > prev
            target = num - prev  # prime must be < target
            prime = get_largest_prime_less_than(target)
            
            if prime != -1:
                prev = num - prime
            else:
                prev = num
        
        return True