计算具有不同素数因子计数的数对（1 到 N 范围内的数字）

给定两个数组 A[] 和 B[]，分别包含 N 个和 M 个整数。我们的任务是找出配对 (A[i], B[j]) 的数量，这些配对能够确保它们的**不同素数因子数量的乘积为偶数**。

示例 1

输入

int arr_A[] = {1, 7}

int arr_B[] = {5, 6}

int N = 2

int M = 2

输出

具有不同素数因子数量偶数乘积的数组对的数量是 1。

解释

对于给定的数组 arr_A[] = {1, 7} 和 arr_B[] = {5, 6}；通过用其独立素数因子的数量替换数组中的每个元素，数组被修改为 arr_A[] = {0, 1} 和 arr_B[] = {1, 2}。因此，{7, 6} 是具有偶数乘积的配对。因此，形成的配对总数为 1。

示例 2

输入

int arr_A[] = {1, 2, 3}

int arr_B[] = {4, 5, 6}

int N = 3

int M = 3

输出

具有不同素数因子数量偶数乘积的数组对的数量是 2。

解释

对于给定的数组 arr_A[] = {1, 2, 3} 和 arr_B[] = {4, 5, 6}；通过用其独立素数因子的数量替换数组中的每个元素，数组被修改为 arr_A[] = {0, 1, 1} 和 arr_B[] = {1, 1, 2}。因此，{{2, 6}, {3, 6}} 是具有偶数乘积的总配对。因此，形成的配对总数为 2。

方法：使用埃拉托斯特尼筛法

该方法使用埃拉托斯特尼筛法有效地计算独立的素数因子。然后，它计算偶数和奇数素数因子的数量，以找出具有素数因子偶数乘积的配对数量。通过利用以下属性，可以使此策略更加有效：两个数字的乘积具有所有数字（直到两个数组中的最大元素）的唯一素数因子数量的优化计算。

奇数 * 奇数 = 奇数

偶数 * 奇数 = 偶数

奇数 * 偶数 = 偶数

偶数 * 偶数 = 偶数

算法

步骤 1：首先，找出 MAX 以下每个数字的独立素数因子，然后将结果存储在名为 countDistinct 的 vector<int> 中。

步骤 2：初始化两个变量，如 evenCnt 和 oddCnt，分别用于保存 arr_B[] 中数组元素的不同素数因子的偶数和奇数数量。

步骤 3：遍历 arr_B[] 数组。

步骤 3.1：如果 count[arr_B[i]] = 0，则继续下一步。如果 count[arr_B[i]] 为奇数，则将 oddCnt 加一。

步骤 3.2：否则，将 evenCnt 加一。

步骤 4：将变量 evenPairs 的值初始化为零。

步骤 5：如果 count[arr_A[i]] 为奇数，则遍历 arr_A[] 数组并将 evenPairs 增加 evenCnt。

步骤 6：否则，将 evenCnt 乘以 oddCnt 以增加 evenPairs。

步骤 7：显示 evenPairs 的值。

实施

文件名：CountPairsWithProducts.java

输出

The number of pairs from an array that form even product with distinct prime factors is 1

复杂度分析

上述代码的时间复杂度为 O(N * log(N))，空间复杂度为 O(N)，其中 N 表示数组的长度。