1000以内约数最多的数是哪个

admin

这是一个简单的统计题，一个很简单的思路是求出1-1000内每个数的约数个数，然后求出最大值
求约数的个数可以类似开关灯问题，只是不去设置灯的开关状态而是记录开关了多少次。

1. #include <iostream>
   
2. using namespace std;
   
3. const int mn=1000;
   
4. bool a[mn+5];
   
5. int i,j;
   
6. int main()
   
7. {
   
8.         for (i=1; i<=mn; i++) a[i]=0; ///预设每个数的约数为0
   
9.         for (i=1; i<=mn; i++)
   
10.                 {
    
11.                         s=0; ///从0开始
    
12.                         for (j=1; j<=mn; j++)
    
13.                                 if (%j==0) s++; ///统计约数个数
    
14.                         a[i]=s;///存起来
    
15.                 }
    
16.         maxs=-1;
    
17.         for (i=1; i<=mn; i++) if (a[i]>maxs) maxs=s;///找最大值
    
18.         cout<<s;
    
19.         return 0;
    
20. }

复制代码

admin

楼上那样做是在是太浪费了，我们完全没有必要记录下所有数的约数个数，其实可以一边求出约数的个数，就一边就和当前的最大值比较，大就保留，小或等就舍弃。

1. #include <iostream>
   
2. using namespace std;
   
3. const int mn=1000;
   
4. int i,j,s,maxs;
   
5. int main()
   
6. {
   
7.         maxs=-1;///maxs赋初值
   
8.         for (i=1; i<=1000; i++)
   
9.                 {
   
10.                         s=0; ///统计赋初值
    
11.                         for (j=1; j<=1000; j++) if (i%j==0) s++; ///统计个数
    
12.                         if (s>maxs)  maxs=s;///擂台比较
    
13.                 }
    
14.         cout<<maxs;
    
15.         return 0;
    
16. }
    

复制代码

admin

要是既想要求出最多约数的个数，又要求出这个数的话，就可以加一个标记变量，在记录maxs的时候同时记录maxi表示这个数，比较的时候只需要比较maxs和s但更新的时候不仅要更新maxs也需要更新maxi

1. #include <iostream>
   
2. using namespace std;
   
3. const int mn=1000;
   
4. int i,j,s,maxs,maxi;
   
5. int main()
   
6. {
   
7.         maxs=-1;///maxs赋初值 maxi不用 想想为什么
   
8.         for (i=1; i<=1000; i++)
   
9.                 {
   
10.                         s=0; ///统计赋初值
    
11.                         for (j=1; j<=1000; j++) if (i%j==0) s++; ///统计个数
    
12.                         if (s>maxs)  {maxs=s;maxi=i;}///更新两个
    
13.                 }
    
14.         cout<<maxs<<' '<<maxi;
    
15.         return 0;
    
16. }
    

复制代码