C/code/合数分解.c

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

#define MAX_N 20

// 函数：检查一个数是否是素数
bool is_prime(int n) {
    if (n <= 1) return false;
    if (n == 2) return true;
    if (n % 2 == 0) return false;
    int i;
    for (i = 3; i * i <= n; i += 2) {
        if (n % i == 0) return false;
    }
    return true;
}

// 函数：对一个数进行质因数分解，并将结果存入集合
void factorize(int n, int* primes, int* prime_count) {
	int i;
    for (i = 2; i * i <= n; i++) {
        if (n % i == 0) {
            while (n % i == 0) {
                n /= i;
            }
            primes[(*prime_count)++] = i;
        }
    }
    if (n > 1) {
        primes[(*prime_count)++] = n;
    }
}

// 函数：对集合中的质因数进行去重
void remove_duplicates(int* primes, int* prime_count) {
    bool unique[MAX_N * 20] = {0};
    int temp[MAX_N * 20];
    int temp_count = 0;
    
    int i;
    
    for (i = 0; i < *prime_count; i++) {
        if (!unique[primes[i]]) {
            unique[primes[i]] = true;
            temp[temp_count++] = primes[i];
        }
    }
    
    for (i = 0; i < temp_count; i++) {
        primes[i] = temp[i];
    }
    
    *prime_count = temp_count;
}

// 函数：比较两个整数的比较器，用于qsort函数
int compare(const void* a, const void* b) {
    return (*(int*)a - *(int*)b);
}

int main() {
    int n;
    scanf("%d", &n);
    int i;
    
    int numbers[MAX_N];
    for (i = 0; i < n; i++) {
        scanf("%d", &numbers[i]);
    }
    
    int primes[MAX_N * 20];
    int prime_count = 0;

    for (i = 0; i < n; i++) {
        factorize(numbers[i], primes, &prime_count);
    }

    remove_duplicates(primes, &prime_count);

    qsort(primes, prime_count, sizeof(int), compare);

    for (i = 0; i < prime_count; i++) {
        printf("%d ", primes[i]);
    }
    printf("\n");

    return 0;
}