1390. Four Divisors

Information

  • Diffculty: Medium

  • Created: 2020-03-22 15:09:25

  • Last Motified: 2020-03-22 15:09:25

  • Tags: 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