diff options
author | Jack Sangdahl <[email protected]> | 2024-12-29 12:11:53 -0700 |
---|---|---|
committer | Jack Sangdahl <[email protected]> | 2024-12-29 12:11:53 -0700 |
commit | 8aedb21321ae40254e4ee6b7fcd4c3de77096964 (patch) | |
tree | 5c5bd32f2e8b7a5f6472e44088184b4db3fa2cbf | |
parent | 6ec780559494acbb28bb161e90963a9e0ce48bc2 (diff) | |
download | leetcode-8aedb21321ae40254e4ee6b7fcd4c3de77096964.tar.gz leetcode-8aedb21321ae40254e4ee6b7fcd4c3de77096964.zip |
2521. distinct prime factors of product of array
-rw-r--r-- | distinct_prime_factors_arr.c | 60 | ||||
-rw-r--r-- | distinct_prime_factors_arr.py | 36 |
2 files changed, 96 insertions, 0 deletions
diff --git a/distinct_prime_factors_arr.c b/distinct_prime_factors_arr.c new file mode 100644 index 0000000..c5d1a9b --- /dev/null +++ b/distinct_prime_factors_arr.c @@ -0,0 +1,60 @@ +// 2521. Distinct Prime Factors of Product of Array +#include "leetcode.h" + +/* + * given an array of positive integers 'nums', return the number of distinct + * prime factors in the product of the element of 'nums'. note that a number + * greater than 1 is called prime if it is divisible by only 1 and itself. an + * integer 'val1' is a factor of another integer 'val2' if 'val2 / val1' is an + * integer + */ + +bool prime(int n) { + if (n <= 1) + return false; + if (n == 2) + return true; + for (int i = 2; i * i <= n; i++) + if (!(n % i)) + return false; + return true; +} + +int *prime_arr(int n, int *return_size) { + int *arr = (int *)malloc(n * sizeof(int)), cnt = 0; + for (int i = 2; i <= n; i++) + if (!(n % i) && prime(i)) { + arr[cnt] = i; + cnt++; + while (!(n % i)) + n /= i; + } + *return_size = cnt; + return arr; +} + +bool contains(int *arr, int arr_size, int n) { + for (int i = 0; i < arr_size; i++) + if (arr[i] == n) + return true; + return false; +} + +int distinctPrimeFactors(int *nums, int numsSize) { + int cnt = 0, arr[10000]; + for (int i = 0; i < numsSize; i++) { + int n = nums[i], tmp, *prime = prime_arr(n, &tmp); + for (int j = 0; j < tmp; j++) + if (!contains(arr, cnt, prime[j])) { + arr[cnt] = prime[j]; + cnt++; + } + } + return cnt; +} + +int main() { + int n1[] = {2, 4, 3, 7, 10, 6}, n2[] = {2, 4, 8, 16}; + printf("%d\n", distinctPrimeFactors(n1, ARRAY_SIZE(n1))); // expect: 4 + printf("%d\n", distinctPrimeFactors(n2, ARRAY_SIZE(n2))); // expect: 1 +} diff --git a/distinct_prime_factors_arr.py b/distinct_prime_factors_arr.py new file mode 100644 index 0000000..c8c9a7a --- /dev/null +++ b/distinct_prime_factors_arr.py @@ -0,0 +1,36 @@ +# 2521. Distinct Prime Factors of Product of Array +from math import sqrt + +""" +given an array of positive integers 'nums', return the number of distinct +prime factors in the product of the element of 'nums'. note that a number +greater than 1 is called prime if it is divisible by only 1 and itself. an +integer 'val1' is a factor of another integer 'val2' if 'val2 / val1' is an +integer +""" + + +class Solution(object): + def distinctPrimeFactors(self, nums): + """ + :type nums: List[int] + :rtype: int + """ + arr = [] + for i in range(len(nums)): + root = int(sqrt(nums[i])) + for num in range(2, root + 1): + if nums[i] % num == 0: + arr.append(num) + while nums[i] % num == 0: + nums[i] = nums[i] // num + if nums[i] >= 2: + arr.append(nums[i]) + arr = set(arr) + return len(arr) + + +if __name__ == "__main__": + obj = Solution() + print(obj.distinctPrimeFactors(nums=[2, 4, 3, 7, 10, 6])) + print(obj.distinctPrimeFactors(nums=[2, 4, 8, 16])) |