编写程序，从控制台读入一组合数（小于等于20个，且每个合数的大小不会超过int数据类型表示的范围），求这些合数分解成素数的最小集

Question

编写程序，从控制台读入一组合数（小于等于20个，且每个合数的大小不会超过int数据类型表示的范围），求这些合数分解成素数的最小集。该最小素数集是所有合数分解成的素数的并集，并且重复的素数只保留一个。按从小到大的顺序输出求得的最小素数集。

【输入形式】

先从控制台输入合数的个数，然后在下一行输入所有合数，各合数之间以一个空格分隔。

【输出形式】

在标准输出上按从小到大顺序输出求得的最小素数集，各素数之间以一个空格分隔，最后一个整数后也可以有一个空格。

【输入样例】

5
20 200 3456650 687 12308760

【输出样例】

2 3 5 29 131 229 257 269

Answer 1

#include<stdio.h>
int b[100000], res[100000];
int isPrime(int n) {
    int i;
    for(i = 2; i * i <= n; i++) {
        if(n % i == 0)
            return 0;
    }
    return 1;
}
int main() {
    int n, t, len = 0, i, j, a;
    scanf("%d", &n);
    for(i = 0; i < n; i++) {
        scanf("%d", &a);
        t = 2;
        while(a != 1) {
            if(a % t == 0 && isPrime(t) ) {
                a /= t;
                if( b[t] == 0) {
                    b[t] = 1;
                    res[len++] = t;
                }
            } else {
                t++;
            }
        }
    }
    for(i = 0; i < len - 1; i++) {
        for(j = 0; j < len - i - 1; j++) {
            if(res[j] > res[j + 1]) {
                t = res[j];
                res[j] = res[j + 1];
                res[j + 1] = t;
            }
        }
    }
    for(i = 0; i < len; i++) {
        printf("%d ", res[i]);
    }
    return 0;
}