设整数n>1,n是目标数指的是:n没有2、3、5之外的素因子。
例如:2、3、5、6、1024、27、125都是目标数;14不是目标数(有素因子7),93不是目标数(有素因子31),101不是目标数(有素因子101)。
找到所有目标数中最小的10000个,并按照从小到大的顺序打印出来。
第 1 条附言 ·
本题目的背景是:面试考官发现候选人的简历上写`熟悉数据结构和基本算法`,故而出此题目。
import time
p=time.time()
s=set({2,3,5})
t=set({})
i=0
j=1
while i<10000:
if j in s:
t.add(j)
s.add(j2)
s.add(j3)
s.add(j*5)
i+=1
if i%100==0:
print(i)
j+=1
t=list(t)
t.sort()
q=time.time()
print(q-p)
print(t)
#12
更多评论
```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()
```
#1
```
#!/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
```
#2