Skip to content

3556. Sum of Largest Prime Substrings 👍

  • Time: $O(n)$
  • Space: $O(n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
 public:
  long long sumOfLargestPrimes(string s) {
    const int n = s.length();
    unordered_set<long> primes;

    for (int i = 0; i < n; ++i)
      for (int j = i + 1; j <= n; ++j) {
        const long num = stol(s.substr(i, j - i));
        if (!primes.contains(num) && isPrime(num))
          primes.insert(num);
      }

    vector<long> sortedPrimes{primes.begin(), primes.end()};
    ranges::sort(sortedPrimes, greater<>());
    return accumulate(
        sortedPrimes.begin(),
        sortedPrimes.begin() + min(3, static_cast<int>(sortedPrimes.size())),
        0L);
  }

 private:
  bool isPrime(long num) {
    if (num <= 1)
      return false;
    for (int i = 2; i <= sqrt(num); ++i)
      if (num % i == 0)
        return false;
    return true;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
  public long sumOfLargestPrimes(String s) {
    final int n = s.length();
    Set<Long> primes = new HashSet<>();

    for (int i = 0; i < n; ++i)
      for (int j = i + 1; j <= n; ++j) {
        final long num = Long.parseLong(s.substring(i, j));
        if (!primes.contains(num) && isPrime(num))
          primes.add(num);
      }

    List<Long> sortedPrimes = new ArrayList<>(primes);
    Collections.sort(sortedPrimes, Collections.reverseOrder());
    return sortedPrimes.stream().limit(3).mapToLong(Long::longValue).sum();
  }

  private boolean isPrime(long num) {
    if (num <= 1)
      return false;
    for (int i = 2; i <= Math.sqrt(num); i++)
      if (num % i == 0)
        return false;
    return true;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution:
  def sumOfLargestPrimes(self, s: str) -> int:
    primes = set()
    n = len(s)

    for i in range(n):
      for j in range(i + 1, n + 1):
        num = int(s[i:j])
        if num not in primes and self._isPrime(num):
          primes.add(num)

    top3 = sorted(primes, reverse=True)[:3]
    return sum(top3)

  def _isPrime(self, n: int) -> bool:
    return n > 1 and all(n % i != 0 for i in range(2, math.isqrt(n) + 1))