题目描述 Description
先输入n,n<=20;再依次输入n个不同的数,每个数<=1000000;找出最大数和最小数,并输出最大最小数的质因数,没有质因数则输出0。
输入描述 Input Description
数n,空行,输入n个数,每个数中间空行;
输出描述 Output Description
最大数的质因数,每个数中间空格; 最小数的质因数,每个数中间空格.
样例输入 Sample Input
2 15 6
样例输出 Sample Output
3 5 2 3
数据范围及提示 Data Size & Hint
无
1 #include<iostream>
2 #include<cstdio>
3 #include<cmath>
4 using namespace std;
5 int a[10001];
6 int maxn=-1;
7 int minn=1000000000;
8 int vis[10000001];
9 int main()
10 {
11 int n;
12 scanf("%d",&n);
13 for(int i=2;i<=sqrt(1000000);i++)
14 {
15 if(vis[i]==0)
16 for(int j=i*i;j<=1000001;j=j+i)
17 {
18 vis[j]=1;
19 }
20 }
21 for(int i=1;i<=n;i++)
22 {
23 scanf("%d",&a[i]);
24 if(a[i]>=maxn)
25 maxn=a[i];
26 if(a[i]<=minn)
27 minn=a[i];
28 }
29 int i=2;
30 int flag=0;
31 int x=maxn;
32 while(maxn/i>0)
33 {
34 if(maxn%i==0&&vis[i]==0&&x!=i)
35 {
36 printf("%d ",i);
37 flag=1;
38 maxn=maxn/i;
39 }
40 i++;
41 }
42 if(flag==0)
43 {
44 printf("0\n");
45 }
46 else
47 {
48 //if(vis[maxn]==0)
49 //printf("%d ",maxn);
50 printf("\n");
51 }
52 flag=0;
53 i=2;
54 int y=minn;
55 while(minn/i>0)
56 {
57 if(minn%i==0&&vis[i]==0&&y!=i)
58 {
59 printf("%d ",i);
60 flag=1;
61 minn=minn/i;
62 }
63 i++;
64 }
65 if(flag==0)
66 {
67 printf("0\n");
68 }
69 else
70 {
71 //if(vis[maxn]==0)
72 //printf("%d ",minn);
73 printf("\n");
74 }
75 return 0;
76 }