leetcode

commit d64836d1bff335bf583b5a3271814586898f3fc4
parent f132056ba8ae6c1164dabad9eceb9c5e587d5ffb
Author: Jack Sangdahl <jack@pngu.org>
Date:   Sat,  3 Jan 2026 19:15:03 -0700

1390. four divisors

Diffstat:
A
four_divisors.c
 | 
49
+++++++++++++++++++++++++++++++++++++++++++++++++
A
four_divisors.py
 | 
48
++++++++++++++++++++++++++++++++++++++++++++++++

2 files changed, 97 insertions(+), 0 deletions(-)
diff --git a/four_divisors.c b/four_divisors.c
@@ -0,0 +1,49 @@
+// 1390. Four Divisors
+#include "leetcode.h"
+
+/*
+ * 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.
+ */
+
+bool prime(int n) {
+  if (n < 2)
+    return false;
+  for (int i = 2; i * i <= n; i++)
+    if (!(n % i))
+      return false;
+  return true;
+}
+
+int sum_one(int n) {
+  int p = (int)round(cbrt(n));
+  if ((long)p * p * p == n && prime(p))
+    return 1 + p + p * p + p * p * p;
+  for (int i = 2; i * i <= n; i++) {
+    if (!(n % i)) {
+      int a = i, b = n / i;
+      if (a != b && prime(a) && prime(b))
+        return 1 + a + b + n;
+      return -1;
+    }
+  }
+  return -1;
+}
+
+int sumFourDivisors(int *nums, int numsSize) {
+  int ans = 0;
+  for (int i = 0; i < numsSize; i++) {
+    int val = sum_one(nums[i]);
+    if (val != -1)
+      ans += val;
+  }
+  return ans;
+}
+
+int main() {
+  int n1[] = {21, 4, 7}, n2[] = {21, 21}, n3[] = {1, 2, 3, 4, 5};
+  printf("%d\n", sumFourDivisors(n1, ARRAY_SIZE(n1))); // expect: 32
+  printf("%d\n", sumFourDivisors(n2, ARRAY_SIZE(n2))); // expect: 64
+  printf("%d\n", sumFourDivisors(n3, ARRAY_SIZE(n3))); // expect: 0
+}
diff --git a/four_divisors.py b/four_divisors.py
@@ -0,0 +1,48 @@
+# 1390. Four Divisors
+
+"""
+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.
+"""
+
+
+class Solution(object):
+    def sum_one(self, n):
+        p = round(n ** (1 / 3))
+        if p**3 == n and self.prime(p):
+            return 1 + p + p * p + p * p * p
+        for i in range(2, int(n**0.5) + 1):
+            if n % i == 0:
+                a, b = i, n // i
+                if a != b and self.prime(a) and self.prime(b):
+                    return 1 + a + b + n
+                return -1
+        return -1
+
+    def prime(self, n):
+        if n < 2:
+            return False
+        for i in range(2, int(n**0.5) + 1):
+            if n % i == 0:
+                return False
+        return True
+
+    def sumFourDivisors(self, nums):
+        """
+        :type nums: List[int]
+        :rtype: int
+        """
+        ans = 0
+        for i in nums:
+            val = self.sum_one(i)
+            if val != -1:
+                ans += val
+        return ans
+
+
+if __name__ == "__main__":
+    obj = Solution()
+    print(obj.sumFourDivisors(nums=[21, 4, 7]))
+    print(obj.sumFourDivisors(nums=[21, 21]))
+    print(obj.sumFourDivisors(nums=[1, 2, 3, 4, 5]))