题解 | #kotori和素因子#

/*
kotori拿到了一些正整数。她决定从每个正整数取出一个素因子。但是，kotori有强迫症，她不允许两个不同的正整数取出相同的素因子。

她想知道，最终所有取出的数的和的最小值是多少？

注：若 a\bmod k== 0amodk==0，则称 kk 是 aa 的因子。若一个数有且仅有两个因子，则称其是素数。显然1只有一个因子，不是素数
*/

#include <stdio.h>
#include<malloc.h>
#include<limits.h>
#include<math.h>

int n;
int min = INT_MAX; //定义最大整数
int* arr;
int* rec;  //用于存放

int isprime(int k) {
    int i = 0;
    for (i = 2; i <= sqrt(k); i++) {
        if (k % i == 0)
            return 0;
    }
    return 1;

}

void dfs(int* arr, int* rec, int index, int sum) {
    int i, j;
    if (index ==n) { // 递归退出条件，找过所有数的素因子。只有递归完所有arr元素才会到这
        if (sum < min)
            min = sum;
        return;
    }

    for (i = 2; i <= arr[index]; i++) {
        if (arr[index] % i == 0 && isprime(i)) { //是arr[index]的素因子？

            int flag = 0; //是否有相同素因子的标志
            for (j = 0; j < index; j++) {

                if (i == rec[j]) { //i在rec里面
                    flag = 1;
                    break;
                }
            }
            if (flag) { //有相同的素因子
                flag = 0;
                continue;

            } else {
                //没有的话继续查找
                rec[index] = i;
                dfs(arr, rec, index + 1, sum + i);
                rec[index] = 0; //回溯
            }
        }
    }
}


int main() {
    int i;
    scanf("%d", &n);
    arr = (int*)malloc(sizeof(int) * n);
    rec = (int*)malloc(sizeof(int) * n);
    for (i = 0; i < n; i++) {
        scanf("%d", &arr[i]);
    }

    dfs(arr, rec, 0, 0);

    if (min < INT_MAX)
        printf("%d", min);
    else
        printf("%d", -1);
    free(arr);
    free(rec);
}