thảo luận Leetcode mỗi ngày

func isPrime(n int) bool {
    if n <= 1 {
        return false
    }
    if n <= 3 {
        return true
    }
    if n%2 == 0 || n%3 == 0 {
        return false
    }

    for i := 5; i*i <= n; i += 6 {
        if n%i == 0 || n%(i+2) == 0 {
            return false
        }
    }
    return true
}

func primeSubOperation(nums []int) bool {
    n := len(nums)

    for i := 0; i < n; i++ {
        for k := nums[i]; k >= 2; k-- {
            r := isPrime(k)
            if i == 0 && r && nums[i]-k > 0 {
                nums[i] = nums[i] - k
                break
            } else if r && nums[i]-k > 0 && nums[i]-k > nums[i-1] {
                nums[i] = nums[i] - k
                break
            }
        }
    }

    for i := 0; i < n-1; i++ {
        if nums[i] == nums[i+1] {
            return false
        }
    }

    return true
}

class Solution {
    func primeSubOperation(_ nums: [Int]) -> Bool {
        var pre = Int.max
        for num in nums.reversed() {
            if num >= pre {
                let prime = smallestPrimeGreaterThan(num - pre)
                if prime < num {
                    pre = num - prime
                } else {
                    return false
                }
            } else {
                pre = num
            }
        }
        return true
    }
    func isPrime(_ n: Int) -> Bool {
        if n <= 1 { return false }
        if n <= 3 { return true }
        if n & 1 == 0 || n % 3 == 0 { return false }
        
        var i = 5
        while i * i <= n {
            if n % i == 0 || n % (i + 2) == 0 {
                return false
            }
            i += 6
        }
        return true
    }
    func smallestPrimeGreaterThan(_ n: Int) -> Int {
        var prime = n + 1
        if !isPrime(prime) && (prime & 1) == 0 {
           prime += 1
        }
        while !isPrime(prime) {
            prime += 2
        }
        return prime
    }
}

maxPrime = 1010
sieve = [1] * (maxPrime)
sieve[1] = 0
for i in range(2, int(math.sqrt(maxPrime)) + 1):
    if sieve[i] == 1:
        for j in range(i * i, maxPrime, i):
            sieve[j] = 0

primes = []
for i in range(2, maxPrime):
    if sieve[i] == 1:
        primes.append(i)

class Solution:
    def findPrime(self, target):
        l, r = 0, len(primes) - 1

        while l <= r:
            pivot = l + (r - l) // 2

            if primes[pivot] > target:
                r = pivot - 1
            else:
                l = pivot + 1

        return primes[l]

    def primeSubOperation(self, nums: List[int]) -> bool:
        for i in range(len(nums) - 2, -1, -1):
            if nums[i + 1] <= 1:
                return False

            if nums[i] >= nums[i + 1]:
                nums[i] -= self.findPrime(nums[i] - nums[i + 1])

        return True if nums[0] > 0 else False

public class Solution {
    public bool isPrime(int k)
    {
        if(k==1)
            return false;

        for(int i = 2; i <= Math.Sqrt(k); i++)
            if(k % i == 0)
                return false;

        return true;
    }

    public int operation(int current, int previous)
    {
        int temp = current;
        for(int i = current-1; i>1; i--)
        {
            if(isPrime(i) && (current - i > previous))
            {
                temp = current - i;
                break;
            }
        }
        return temp;
    }

    public bool PrimeSubOperation(int[] nums) {
        nums[0] = operation(nums[0],0);
        for(int i = 1; i<nums.Length; i++)
        {
            nums[i] = operation(nums[i], nums[i-1]);
            if(nums[i] <= nums[i-1])
                return false;
        }       
        return true;
    }
}