Approach

# Prime
先建質數表、分解後看是不是4個因數
如果是用兩個質數判斷，注意1 2 4 8 = 8這一種的例外

Time Complexity

O(N ∗ Sqrt(M))

Space Complexity

O(N * Sqrt(M))

Code

class Solution {
public:
    void make_prime_table(vector<int>& prime, int num) {
        prime.push_back(2);
        prime.push_back(3);

        for (int i = 5 ; i <= sqrt(num) ; i+=2) {
            bool ok = true;

            for (int j = 0 ; j < prime.size() && prime[j] <= sqrt(i) ; j++) {
                if (i % prime[j] == 0) {
                    ok = false;
                }
            }

            if (ok) {
                prime.push_back(i);
            }
        }
    }

    int sumFourDivisors(vector<int>& nums) {
        vector<int> prime;
        make_prime_table(prime, 100000);

        /*
        for (int i = 0 ; i < prime.size() ; i++) {
            cout << prime[i] << endl;
        }
        21 = 1 3 7 21
        8  = 1 2 4 8
        */

        int ans = 0;
        for (int i = 0 ; i < nums.size() ; i++) {
            int div1 = 0, div2 = 0, cnt = 0;

            for (int j = 0 ; j < prime.size() && prime[j] <= sqrt(nums[i]) ; j++) {
                if (nums[i] % prime[j] == 0) {
                    div1 = prime[j];
                    div2 = nums[i] / prime[j];
                    cnt++;
                }
            }

            if (cnt == 1 && (div1 != div2)) {
                bool div2_is_prime = true;

                for (int j = 0 ; j < prime.size() && prime[j] <= sqrt(div2) ; j++) {
                    if (div2 % prime[j] == 0) {
                        if (div2 / prime[j] != prime[j]) {
                            div2_is_prime = false;
                            break;
                        };
                    }
                }

                if (div2_is_prime == true) {
                    //printf("%d %d %d %d\n", 1, div1, div2, nums[i]);
                    ans = ans + (1 + div1 + div2 + nums[i]);
                }
            }
        }

        return ans;
    }
};