某企业招聘题目：获取最小的10000个素因子只有2、3、5的数

这个最好使用一个动态遍历的、有序的、插入耗时短的结构，来保存候选数字。 然后我们就可以一边生成候选数字，存入这个结构，一边从这个结构里按从小到大的顺序取出数字就行了。 个人觉得最合适的数据结构，就是跳表。插入时间Nlog(N)，遍历时更是log(1)的复杂度。 双向链表和平衡二叉查找树的复合数据结构也很合适。 不知道python里有没有。 我自己的库里倒是有两个。只要采用了合适的数据结构，代码反而很简单。 跳表版本（这个跳表采用int64+string作为键，值为interface{}） package main import ( "fmt" "github.com/hydra13142/container/skiplist" "os" ) type Void = struct{} func main() { t := skiplist.New() for i := 2; i < 6; i++ { t.Insert(int64(i), "", Void{}) } p := t.SearchByIndex(0) xs := [10000]int64{} for i := 0; i < 10000; i++ { k, _ := p.Key() xs[i] = k t.Insert(k*2, "", Void{}) t.Insert(k*3, "", Void{}) t.Insert(k*5, "", Void{}) p.Next() } file, _ := os.Create("output2.txt") defer file.Close() fmt.Fprintln(file, xs) } 二叉树版本（SBT树采用int64作为键，值为interface{}） package main import ( "fmt" "github.com/hydar13142/container/sbt" "os" ) type Void = struct{} func main() { t := sbt.NewSBT() for i := 2; i < 6; i++ { t.Insert(int64(i), Void{}) } p := t.Index(0) xs := [10000]int64{} for i := 0; i < 10000; i++ { k := p.Key() xs[i] = k t.Insert(k*2, Void{}) t.Insert(k*3, Void{}) t.Insert(k*5, Void{}) // t.DeleteNode(p) 删不删节点都不影响结果 p = p.Next() } file, _ := os.Create("output.txt") defer file.Close() fmt.Fprintln(file, xs) }

```python #! /usr/bin/env python def mul_nums(nums,size): curnums = [] retnums = [] minnum = nums[0] for c in nums: curnums.append(c) retnums.append(c) if c < minnum: minnum = c i = len(retnums) while i < size: minnum = curnums[0] minidx = 0 idx = 0 for c in curnums: if c < minnum: minnum = c minidx = idx idx += 1 minmulnum = curnums[0] * nums[0] for c in curnums: for d in nums: if (c * d) < minmulnum: minmulnum = (c * d) retnums.append(curnums[minidx]) curnums[minidx] = minmulnum i += 1 return retnums def main(): retnums = mul_nums([2,3,5],10000) for c in retnums: print('[%d]\n'%(c)) main() ```

``` #!/usr/bin/env python # -*- coding:utf-8 -*- """ 10000以内 素因子只有2,3,5的数 只需要log2(10000) * log3(10000)*log5(10000)次循环 520次 最终的数据个数小于这个数 """ import math def findOnly235(): max = 10000 maxL2 = int(math.log(max, 2)) maxL3 = int(math.log(max, 3)) maxL5 = int(math.log(max, 5)) print maxL2, maxL3, maxL5 L = [] for i in range(maxL2): for j in range(maxL3): for k in range(maxL5): number = pow(2, i) * pow(3, j) * pow(5, k) if number <= max and number > 1: L.append(number) return L if __name__ == '__main__': l = findOnly235() l.sort() print l ```