Re: [閒聊] 每日leetcode

[dont (dont)]

2601. Prime Subtraction Operation

## 思路

假如新遞增陣列的前一個值是prev,
下一個值 num-prime 要大於 prev

=> 先建質數表, 掃陣列用Binary Search找最大可能的prime 並更新prev

## Code

```python
class Solution:
    def primeSubOperation(self, nums: List[int]) -> bool:

        is_prime = [True] * 1001
        is_prime[0] = is_prime[1] = False
        for i in range(2, int(sqrt(1001)) + 1):
            if not is_prime[i]:
                continue
            for j in range(2*i, 1001, i):
                is_prime[j] = False

        primes = [i for i in range(2, 1001) if is_prime[i]]

        prev = 0
        for num in nums:
            if num <= prev:
                return False
            idx = bisect_left(primes, num - prev) - 1
            prev = num - primes[idx] if idx != -1 else num

        return True
```

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 185.213.82.158 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1731330217.A.7D4.html
→ DJYOMIYAHINA: 大師
→ sustainer123: 大師
推 CP3isgood: 大師
→ JerryChungYC: 剩我什麼都不會了
→ sixB: 酷 沒想到可以二分搜