# 2601. Prime Subtraction Operation
###### tags: `Leetcode` `Medium` `Math` `Binary Search` `Greedy`
Link: https://leetcode.com/problems/prime-subtraction-operation/description/
## 思路
先用sieve algorithm找到所有小于1000的prime number(nums里面的数字都小于1000)
然后对于每个nums[i] 我们都要让它尽可能最小
如果它已经小于我们做完操作的nums[i] 那么我们就无法把整个array变成increasing的
我们需要找到一个小于nums[i]-nums[i-1]的最大的prime number
如果找不到就用nums[i]本身
## Code

class Solution:
    def primeSubOperation(self, nums: List[int]) -> bool:
        isPrime = [True]*1001

        def sieve(isPrime: List[bool]):
            isPrime[0] = isPrime[1] = False
            for i in range(2, math.ceil(math.sqrt(1001))+1):
                for j in range(2*i, 1001, i):
                    isPrime[j] = False
        
        sieve(isPrime)
        primes = []
        for i in range(len(isPrime)):
            if isPrime[i]: primes.append(i)
 
        prev = 0
        for num in nums:
            if prev>=num: return False
            start, end = 0, len(primes)
            while start<end:
                mid = start+(end-start)//2
                if primes[mid]<num-prev: start = mid+1
                else: end = mid
            # if start==0: return False
            if start!=0: prev = num-primes[start-1]
            else: prev = num
        return True