# LeetCode 2601. Prime Subtraction Operation

https://leetcode.com/problems/prime-subtraction-operation/description/

## 題目大意

給定整數陣列 `nums` ，對於 `nums[i]` 我們可以減去嚴格小於它的質數
試問能否透過這樣的操作使得 `nums` 變為嚴格遞增？

## 思考

1 - 1000 的質數有 168 個


C++ 參考解答：

class Solution
{
public:
    bool primeSubOperation(vector<int> &nums)
    {
        const int n = nums.size();
        const auto primes = generatePrimes();

        int prevNum = 0;
        for (int &num : nums)
        {
            auto it = lower_bound(primes.begin(), primes.end(), num - prevNum);
            if (it != primes.begin() && (num - *prev(it) > prevNum))
                num -= *prev(it);

            if (num <= prevNum)
                return false;

            prevNum = num;
        }

        return true;
    }

private:
    array<int, 168> generatePrimes()
    {
        const int kMax = 1000;
        array<int, 168> primes{};
        bitset<kMax> isPrime;
        isPrime.set();

        for (int i = 2, idx = 0; i < kMax; ++i)
        {
            if (isPrime[i])
            {
                primes[idx++] = i;
                for (int j = i * i; j < kMax; j += i)
                {
                    isPrime[j] = false;
                }
            }
        }

        return primes;
    }
};

Go 參考解答：

func generatePrimes(limit int) []int {
	isPrime := make([]bool, limit)
	for i := 2; i < limit; i++ {
		isPrime[i] = true
	}

	for i := 2; i*i < limit; i++ {
		if isPrime[i] {
			for j := i * i; j < limit; j += i {
				isPrime[j] = false
			}
		}
	}

	primes := []int{}
	for i := 2; i < limit; i++ {
		if isPrime[i] {
			primes = append(primes, i)
		}
	}
	return primes
}

func primeSubOperation(nums []int) bool {
	const maxPrime = 1000
	primes := generatePrimes(maxPrime)

	prevNum := 0
	for i, num := range nums {
		target := num - prevNum
		idx := sort.Search(len(primes), func(j int) bool { return primes[j] >= target })

		if idx > 0 && num-primes[idx-1] > prevNum {
			nums[i] -= primes[idx-1]
		}

		if nums[i] <= prevNum {
			return false
		}

		prevNum = nums[i]
	}

	return true
}