C/code/加强训练任务/合数分解.c

#include <stdio.h>
#include <stdbool.h>

// 判断一个数是否为素数
bool isPrime(int num) {
    if (num <= 1) return false;
    if (num <= 3) return true;
    if (num % 2 == 0 || num % 3 == 0) return false;
    int  i;
    for (i = 5; i * i <= num; i += 6) {
        if (num % i == 0 || num % (i + 2) == 0)
            return false;
    }
    return true;
}

// 打印素数分解结果的最小素数集
void printMinimumPrimeSet(int *compositeNumbers, int numCount) {
    // 使用集合来存储最小素数集，利用集合的自动去重和排序特性
    bool primeSet[100000] = { false }; // 使用一个足够大的数组来存储素数集合
    int maxNum = 0;

    // 找出所有的素数因子
    int i, k;
    for (k = 0; k < numCount; ++k) {
        int num = compositeNumbers[k];
        if (isPrime(num)) {
            primeSet[num] = true;
            if (num > maxNum) maxNum = num;
        } else {
            int factor = 2;
            while (num > 1) {
                if (isPrime(factor) && num % factor == 0) {
                    primeSet[factor] = true;
                    num /= factor;
                    factor = 2; // 重新从最小素数开始找因子
                } else {
                    factor++;
                }
            }
            if (factor > maxNum) maxNum = factor;
        }
    }

    // 输出最小素数集，按从小到大顺序输出
    bool first = true;
    for (i = 2; i <= maxNum; ++i) {
        if (primeSet[i]) {
            if (!first) printf(" ");
            printf("%d", i);
            first = false;
        }
    }
    printf("\n");
}

int main() {
    int numCount;
    scanf("%d", &numCount);

    int compositeNumbers[20];
    int i;
    for (i = 0; i < numCount; ++i) {
        scanf("%d", &compositeNumbers[i]);
    }

    printMinimumPrimeSet(compositeNumbers, numCount);

    return 0;
}