2804 最大最小数质因数

题目描述 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

无

分类标签 Tags 点此展开

 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
");
45     }
46     else
47     {
48         //if(vis[maxn]==0)
49         //printf("%d ",maxn);
50         printf("
");
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
");
68     }
69     else
70     {
71         //if(vis[maxn]==0)
72         //printf("%d ",minn);
73         printf("
");
74     }
75     return 0;
76 }