总时间限制: 1000ms 内存限制: 65536kB描述
任意输入两个正整数m, n (1 < m < n <= 5000),依次输出m到n之间每个数的最大质因子(包括m和n;如果某个数本身是质数,则输出这个数自身)。
输入一行,包含两个正整数m和n,其间以单个空格间隔。输出一行,每个整数的最大质因子,以逗号间隔。样例输入
5 10
样例输出
5,3,7,2,3,5
来源元培-From Whf
1 #include<iostream>
2 #include<cstdio>
3 #include<cmath>
4 using namespace std;
5 int vis[10001];
6 int main()
7 {
8 int m,n;
9 cin>>m>>n;
10 for(int i=2;i<=sqrt(n+0.5);i++)
11 {
12 if(vis[i]==0)
13 {
14 for(int j=i*i;j<=n;j=j+i)
15 {
16 vis[j]=1;
17 }
18 }
19 }
20 int flag=0;
21 for(int i=m;i<=n;i++)
22 {
23 if(vis[i]==0&&flag==1)
24 {
25 cout<<","<<i;
26 }
27 else if(vis[i]==0&&flag==0)
28 {
29 cout<<i;
30 flag=1;
31 }
32 else
33 {
34 for(int j=i-1;j>=2;j--)
35 {
36 if(i%j==0&&vis[j]==0)
37 {
38 if(flag==1)
39 cout<<","<<j;
40 else
41 {
42 cout<<j;
43 flag=1;
44 }
45 break;
46 }
47
48 }
49 }
50 }
51 return 0;
52 }