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

优化了一下，1、修改数组为数组切片，这样直接使用copy,不再自己一个个移动赋值复制。2、优化了查找方法 ``` package suanfa import ( "fmt" "time" ) //获取前10000个素因子只有2 3 5的数 主要的优化 1、数组移动改为切片，整段copy 不再一个个赋值移动 //2、改动查找i2 i3的方法，根据上次的查找i2 i3的下标来查，实际每次查找1-2次 func Run4() { a := make([]uint64, 10002) a[0] = 2 a[1] = 3 a[2] = 5 maxi := 2 //最大值的索引 start2 := 0 start3 := 0 var a2 uint64 var a3 uint64 var a5 uint64 p := time.Now() for i := 0; i < 9999; i++ { c := a[i] a2 = c * 2 if a[9999] != 0 && a2 >= a[9999] { break } a3 = c * 3 a5 = c * 5 start2, start3, maxi = sortInsert4(a, a2, a3, a5, start2, start3, maxi) //插入3个数 //fmt.Println(a[:maxi+1]) } q := time.Now() fmt.Println(q.Sub(p).Nanoseconds()) //fmt.Println(a[:maxi+1]) fmt.Println(a[9999]) } func sortInsert4(a []uint64, a2 uint64, a3 uint64, a5 uint64, start2 int, start3 int, maxi int) (int, int, int) { //fmt.Println(a2, a3, a5, start2, start3, maxi) //a5肯定在最后。 插入a2和a3 查找 从后往前移动插入 i2 := 0 i3 := 0 //插入的数量 是1或者2 insert := 0 //搜索i2的位置 i := 0 for i = start2; i <= maxi; i++ { if a2 <= a[i] { break } } if a2 != a[i] { insert++ } i2 = i //搜索i3的位置 实际顶多比较几次就找到 for i = start3; i <= maxi; i++ { if a3 <= a[i] { break } } if a3 != a[i] { insert++ } i3 = i //fmt.Println(start2, i2, start3, i3, maxi) //由这打印出的可以看出，每次查找i2 i3顶多查找1-2次 if maxi+insert <= 9999 { copy(a[i3+insert:maxi+insert+1], a[i3:maxi+1]) } else if i3+insert <= 9999 { copy(a[i3+insert:9999], a[i3:10000]) } maxi = maxi + insert if a[i3] != a3 { insert-- a[i3+insert] = a3 } if insert != 0 { copy(a[i2+1:i3+1], a[i2:i3]) a[i2] = a2 } //fmt.Println(a[:maxi+1]) maxi++ if maxi <= 9999 { a[maxi] = a5 //a5一定是最大值，追加在末尾 } else { maxi = 9999 } return i2, i3, maxi } ``` 优化后在我电脑上计算到第10000个在1毫秒内。

```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 ```