Four Divisors

Problem Description

Given an integer array nums, return the sum of divisors of the integers in that array that have exactly four divisors. If there is no such integer in the array, return 0.

Key Insights

• A number has exactly four divisors if it is of the form p^3 (where p is a prime number) or p * q (where p and q are distinct prime numbers).
• We need to identify numbers in the array that fit one of these two forms to calculate their divisors.
• Efficiently checking for divisors will help in reducing computation time, especially for larger numbers.

Space and Time Complexity

Time Complexity: O(n * sqrt(m)), where n is the length of the nums array and m is the maximum value in nums.
Space Complexity: O(1), as we are using a constant amount of extra space.

Solution

To solve the problem, we will:

1. Iterate through each number in the nums array.
2. For each number, we will determine if it has exactly four divisors by checking its potential forms (either p^3 or p * q).
3. If a number has exactly four divisors, we will sum those divisors.
4. Finally, return the total sum of divisors for all qualifying numbers.

We will use a loop to count divisors and a nested loop for checking prime pairs, ensuring efficient prime checking.

Code Solutions