首页 > > 程序设计 > C/C++ >

21:最大质因子序列

2018-06-17 23:06:51来源：未知阅读 ()

21:最大质因子序列

查看
提交
统计
提问

总时间限制:: 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 }