123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990 |
- #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;
- }
|