Four Divisors

Problem Id: 1390 Difficulty: Medium Tag: Math


Intuition

First, we could get a prime list less than 10^5. Then, for each num, we could test all primes which his less than or equal to num ^ (1 / 2) to see if num / p is in the prime list.

Solution


class Solution:
    @staticmethod
    def isPrime(num):
        for i in range(2, min(int(num ** (1 / 2)) + 1, num)):
            if num % i == 0:
                return False
        return True

    def sumFourDivisors(self, nums: List[int]) -> int:
        primes = [num for num in range(2, 10 ** 5 + 1) if self.isPrime(num)]
        primes_set = set(primes)

        s = 0
        for num in nums:
            for p in primes:
                if p * p >= num:
                    break
                elif p * p * p == num:
                    s += num + p * p + p + 1
                    break
                elif num % p == 0 and num // p in primes_set:
                    s += num + p + num // p + 1
                    break
        return s