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

#include <stdio.h>
#include <stdlib.h>

// 函数：判断一个数是否为素数
int is_prime(int num) {
	int i;
    if (num <= 1) return 0;
    if (num == 2) return 1;
    if (num % 2 == 0) return 0;
    for (i = 3; i * i <= num; i += 2) {
        if (num % i == 0) return 0;
    }
    return 1;
}

// 函数：获取一个数的所有素数因子
void get_prime_factors(int num, int *factors, int *count) {
    int factor = 2;
    while (num > 1) {
        if (num % factor == 0) {
            factors[*count] = factor;
            (*count)++;
            num /= factor;
        } else {
            factor++;
            while (!is_prime(factor)) {
                factor++;
            }
        }
    }
}

int main() {
	int i,j;
    int num;

    scanf("%d", &num);

    if (num <= 1) {
        printf("输入的数必须大于1且为合数。\n");
        return 1;
    }

    int factors[32];  // 假设最大int的素数因子数量不会超过32个
    int count = 0;

    get_prime_factors(num, factors, &count);

    int occurrences[32] = {0};  // 用于记录每个素数因子的出现次数
    int unique_factors[32];     // 记录所有唯一的素数因子
    int unique_count = 0;

    for (i = 0; i < count; i++) {
        int factor = factors[i];
        int found = 0;
        for (j = 0; j < unique_count; j++) {
            if (unique_factors[j] == factor) {
                occurrences[j]++;
                found = 1;
                break;
            }
        }
        if (!found) {
            unique_factors[unique_count] = factor;
            occurrences[unique_count] = 1;
            unique_count++;
        }
    }

    // 输出只出现一次的素数因子
    for (i = 0; i < unique_count; i++) {
        if (occurrences[i] == 1) {
            printf("%d ", unique_factors[i]);
        }
    }
    printf("\n");

    return 0;
}