Kotlin程序员算法宝典：求有序数列的第1500个数

【出自WR面试题】

难度系数：★★★★☆ 被考察系数：★★★☆☆

题目描述：

一个有序数列，序列中的每一个值都能够被2或者3或者5所整除，求第1500个值是多少。

分析与解答：

方法一：蛮力法

最简单的方法就是用一个计数器来记录满足条件的整数的个数，然后从1开始遍历整数，如果当前遍历的数能被2或者3或者5整除，则计数器的值加1，当计数器的值为1500时，当前遍历到的值就是所要求的值。根据这个思路实现代码如下：(www.xing528.com)

程序的运行结果如下：

2045

方法二：数字规律法

首先可以很容易得到2、3和5的最小公倍数为30，此外，1～30这个区间内满足条件的数有22个{2，3，4，5，6，8，9，10，12，14，15，16，18，20，21，22，24，25，26，27，28，30}，由于最小公倍数为30，可以猜想，满足条件的数字是否具有周期性（周期为30）呢？通过计算可以发现，31～60这个区间内满足条件的数也恰好有22个{32，33，34，35，36，38，39，40，42，44，45，46，48，50，51，52，54，55，56，57，58，60}，从而发现这些满足条件的数具有周期性（周期为30）。由于1500/22=68，1500%68=4，从而可以得出第1500个数经过了68个周期，然后在第69个周期中取第四个满足条件的数{2，3，4，5}。从而可以得出第1500个数为68*30+5=2045。根据这个思路实现代码如下：

算法性能分析：

方法二的时间复杂度为O（1），此外，方法二使用了22个额外的存储空间。方法二的计算方法可以用来分析方法一的执行效率，从方法二的实现代码可以得出，方法一中循环执行的次数为（N/22）*30+a[N%22]，其中，a[N%22]的取值范围为2～30，因此方法一的时间复杂度为O（N）。