求形如 2^r*3^s*5^t 的整数序列

gxqcn

求前 200 项可表示成 $2^r*3^s*5^t$ （r,s,t 均为整数）的自然数序列。

• 请证明：以上序列最大值小于 $2^30$；
• 请用 C / C++ 语言编程输出该序列，要求算法的空间及时间复杂度尽可能地低。
  

附注：可解除须 C / C++ 的限定，欢迎大家用自己熟悉的计算机语言提交代码。

gxqcn

两年前我给公司面试题库出了几道算法题，但迄今几乎无人可正确作答，
上述题目是在某面试题基础上再升级的，难度有所提高，因为咱们论坛里高手多。

mathematica

假设r\s\t是正整数,那么这个数必然是2*3*5=30的倍数,然后乘以2/4/8/16/32/.............
3/9/27/................
5/25/125.............

mathematica

(r+1)*(s+1)*(t+1)<=200

mathematica

1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 16, 18, 20, 24, 25, 27, 30, 32,
36, 40, 45, 48, 50, 54, 60, 64, 72, 75, 80, 81, 90, 96, 100, 108,
120, 125, 128, 135, 144, 150, 160, 162, 180, 192, 200, 216, 225, 240,
243, 250, 256, 270, 288, 300, 320, 324, 360, 375, 384, 400, 405, 432,
450, 480, 486, 500, 512, 540, 576, 600, 625, 640, 648, 675, 720, 729,
750, 768, 800, 810, 864, 900, 960, 972, 1000, 1024, 1080, 1125, 1152,
1200, 1215, 1250, 1280, 1296, 1350, 1440, 1458, 1500, 1536, 1600,
1620, 1728, 1800, 1875, 1920, 1944, 2000, 2025, 2048, 2160, 2187,
2250, 2304, 2400, 2430, 2500, 2560, 2592, 2700, 2880, 2916, 3000,
3072, 3125, 3200, 3240, 3375, 3456, 3600, 3645, 3750, 3840, 3888,
4000, 4050, 4096, 4320, 4374, 4500, 4608, 4800, 4860, 5000, 5120,
5184, 5400, 5625, 5760, 5832, 6000, 6075, 6144, 6250, 6400, 6480,
6561, 6750, 6912, 7200, 7290, 7500, 7680, 7776, 8000, 8100, 8192,
8640, 8748, 9000, 9216, 9375, 9600, 9720, 10000, 10125, 10240, 10368,
10800, 10935, 11250, 11520, 11664, 12000, 12150, 12288, 12500, 12800,
12960, 13122, 13500, 13824, 14400, 14580, 15000, 15360, 15552, 15625,
16000, 16200
是这些数吗?如果r\s\t可以是零的话

gxqcn

mathematica 发表于 2013-10-18 10:26
(r+1)*(s+1)*(t+1)<=200

如果是为了证明第1问，
则基本上踩在点子上了，
即构造一整数 $2^r*3^s*5^t < 2^30$， 且满足 $(r+1)(s+1)(t+1)>=200$ 即可。

比如：$2^6*3^6*5^6 = 30^6 < 32^6 = 2^30$，而 $7^3 = 343 > 200$。

此问的目的，仅仅提示：在用32位系统下，所求序列选用 int 型数据类型足矣（不会溢出；即：无需大整数运算）。

mathematica

如果rst必须大于零,那么是
30, 60, 90, 120, 150, 180, 240, 270, 300, 360, 450, 480, 540, 600,
720, 750, 810, 900, 960, 1080, 1200, 1350, 1440, 1500, 1620, 1800,
1920, 2160, 2250, 2400, 2430, 2700, 2880, 3000, 3240, 3600, 3750,
3840, 4050, 4320, 4500, 4800, 4860, 5400, 5760, 6000, 6480, 6750,
7200, 7290, 7500, 7680, 8100, 8640, 9000, 9600, 9720, 10800, 11250,
11520, 12000, 12150, 12960, 13500, 14400, 14580, 15000, 15360, 16200,
17280, 18000, 18750, 19200, 19440, 20250, 21600, 21870, 22500, 23040,
24000, 24300, 25920, 27000, 28800, 29160, 30000, 30720, 32400, 33750,
34560, 36000, 36450, 37500, 38400, 38880, 40500, 43200, 43740, 45000,
46080, 48000, 48600, 51840, 54000, 56250, 57600, 58320, 60000, 60750,
61440, 64800, 65610, 67500, 69120, 72000, 72900, 75000, 76800, 77760,
81000, 86400, 87480, 90000, 92160, 93750, 96000, 97200, 101250,
103680, 108000, 109350, 112500, 115200, 116640, 120000, 121500,
122880, 129600, 131220, 135000, 138240, 144000, 145800, 150000,
153600, 155520, 162000, 168750, 172800, 174960, 180000, 182250,
184320, 187500, 192000, 194400, 196830, 202500, 207360, 216000,
218700, 225000, 230400, 233280, 240000, 243000, 245760, 259200,
262440, 270000, 276480, 281250, 288000, 291600, 300000, 303750,
307200, 311040, 324000, 328050, 337500, 345600, 349920, 360000,
364500, 368640, 375000, 384000, 388800, 393660, 405000, 414720,
432000, 437400, 450000, 460800, 466560, 468750, 480000, 486000

mathematica

1. (*求前200个2/3/5的幂的整数*)
   
2. Clear["Global`*"];(*Clear all variables*)
   
3. fun[n0_]:=Module[{n=n0,s2,s3,s5,out},
   
4.                  s2=0;While[Mod[n,2]==0,s2=s2+1;n=n/2];(*不断地除以2*)
   
5.                  s3=0;While[Mod[n,3]==0,s3=s3+1;n=n/3];(*不断地除以3*)
   
6.                  s5=0;While[Mod[n,5]==0,s5=s5+1;n=n/5];(*不断地除以5*)
   
7.                  (*如果正好只是2/3/5的倍数,则n应该=1*)
   
8.                  If[n==1,out=1,out=0];
   
9.                  out
   
10.                 ]
    
11. Select[Range@500000,fun[#]==1&][[1;;200]]
    

复制代码

gxqcn

在 6# 里，我只是随便构造了一个数来证明。

请你帮忙找一下：$2^32$ 以内，序列里素因子数目最多的那个数是哪个？
即：$n=2^r*3^s*5^t < 2^32$ 且使 $(r+1)(s+1)(t+1)$ 最大？

mathematica

1. #include <iostream>
   
2. using namespace std;
   
3. int myfun(long n);
   
4. int main()
   
5. {
   
6.         int k=0;//用来计算到底有多少个满足条件的整数
   
7.         //先取一个较大的上限,如果满足条件,自动中断循环
   
8.     for (long i=1;i<=800000;i++)
   
9.     {
   
10.                 if (myfun(i)==1)
    
11.                 {
    
12.                         printf("%d\n",i);
    
13.                         k++;
    
14.                 }
    
15.                 if (k>=200)
    
16.                 {
    
17.                         break;
    
18.                 }
    
19.     }
    
20.         return 0;
    
21. }
    
22. //子函数,用来判定整数是否满足要求,如果满足要求则返回1,如果不满足x则返回0
    
23. int myfun(long n)
    
24. {
    
25.         int out;
    
26.         while (n%2==0) { n=n/2; }
    
27.         while (n%3==0) { n=n/3; }
    
28.         while (n%5==0) { n=n/5; }
    
29.         //如果只可能含有2/3/5因数,那么n最后应该等于1
    
30.         if (n==1)
    
31.         {
    
32.                 out=1;
    
33.         }
    
34.         else
    
35.         {
    
36.                 out=0;
    
37.         }
    
38.         return out;
    
39. }
    
40. 
    

复制代码

上面是我写的c++代码,结果和上面应该一样,一两秒钟就能搞定了,c++的效率挺高的!