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 /distinct_prime_factors_arr.c | |
parent | 6ec780559494acbb28bb161e90963a9e0ce48bc2 (diff) | |
download | leetcode-8aedb21321ae40254e4ee6b7fcd4c3de77096964.tar.gz leetcode-8aedb21321ae40254e4ee6b7fcd4c3de77096964.zip |
2521. distinct prime factors of product of array
Diffstat (limited to 'distinct_prime_factors_arr.c')
-rw-r--r-- | distinct_prime_factors_arr.c | 60 |
1 files changed, 60 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 +} |