LeetCode 3556. Sum of Largest Prime Substrings

biweekly contest 157。

題目

https://leetcode.com/problems/sum-of-largest-prime-substrings/

解法

暴力枚舉子陣列，判斷是否為質數。
排序找前三大的質數即可。

時間複雜度 O(N^2 * sqrt(MX))，其中 MX = 10^10。
空間複雜度 O(N^2)。

class Solution:
    def sumOfLargestPrimes(self, s: str) -> int:
        N = len(s)
        p = set()
        for i in range(N):
            x = 0
            for j in range(i, N):
                x = x*10 + int(s[j])
                if is_prime(x):
                    p.add(x)

        return sum(sorted(p)[-3:])


# check is prime or not
# O(sqrt(n))
def is_prime(n):
    for i in range(2, int(n ** 0.5) + 1):
        if n % i == 0:
            return False
    return n >= 2