LeetCode 1390. Four Divisors

https://leetcode.com/problems/four-divisors

 

 

각 수들의 가장 작은 소인수(p)를 전처리해주고, 각 수(num)를 순회하면서 q = num / p를 구해줍니다.

q도 소수이고 p != q 이라면, num의 약수는 (1, p, q, num)으로 총 4개가 됩니다.

또는, num = p^3 이라면, num의 약수는 (1, p, q(=p*p), num)으로 총 4개가 됩니다.

class Solution {
public:
    int spf[100001] = {0};

    int sumFourDivisors(vector<int>& nums) {
        int maxNum = nums[0];
        for(int num : nums) {
            maxNum = max(maxNum, num);
        }
        
        for(int i=2; i<=maxNum; i++) {
            if (spf[i]) continue;
            for(int j=i; j<=maxNum; j+=i) {
                if(!spf[j]) spf[j] = i;
            }
        }

        int res = 0;
        for(int num : nums) {
            if (num < 6) continue;

            int p = spf[num];
            int q = num / spf[num];

            if(spf[q] == q && p != q) {
                // p * q == num
                res += 1 + p + q + num;
            } else if(q % p == 0 && q / p == p) {
                // p^3 == num
                res += 1 + p + q + num;
            }
        }
        return res;
    }
};