鱼C论坛Python精英挑战赛（第二季02期）

jerryxjr1220

鱼C论坛Python精英挑战赛第二季又开始啦！

本季挑战赛依旧会有精彩的题目供大家挑战，大量鱼币奖励等你赢取！

                               
登录/注册后可看大图

本期题目：汉明数

汉明数是指没有大于5的质因子组成的正整数，所以前几个汉明数是1，2，3，4，5，6，8，9，10，12，15.

100以内（包含100）共有34个汉明数，而10**8以内（包含10**8）共有1105个汉明数。

问10**100以内（包含10**100）共有多少汉明数？

注：通过本题可以体会python对于大数运算的优势，要是换成其他语言，10**100的计算可能就会导致溢出了。

比赛规则：
本题为纯算法题，要求输出结果正确，运行时间最短的鱼油即为优胜者。比赛截止日期：8月14日24时。

优胜者奖励100鱼币，由@小甲鱼 老师倾情赞助！

@冬雪雪冬 @～风介～ @SixPy

冬雪雪冬

抛砖引玉吧，这个没有优化，我的机器上用时25s，希望能看到大家优秀的程序。

'''先说说思路，既然这个数是2，3，5因子组成的，那么此数必然是2的倍数乘3的倍数乘5的倍数。
2的倍数不超过2**n2 > 1e100，3和5一样。
依次做3重循环如果不大于1e100，就统计一次。'''
import math
n2 = int(math.log2(1e100)) + 1 #计算2的倍数上限，下同，
n3 = int(math.log2(1e100)/math.log2(3)) + 1 #其实用log10更方便1e100都不用算了
n5 = int(math.log2(1e100)/math.log2(5)) + 1
count = 0
for i2 in range(n2):
    for i3 in range(n3):
        for i5 in range(n5):
            if (2 ** i2) * (3 ** i3) * (5 ** i5) <= 1e100:
                count += 1
print(count)

结果是1697191，不知对不对？

冬雪雪冬

优化一下，用时减少到3s多
思路与前面一样，这里用对数来计算，把乘方变成了乘法，把乘法变成了加法，所以计算效率提高。

import math
n2 = int(math.log2(1e100)) + 1
n3 = int(math.log2(1e100)/math.log2(3)) + 1
n5 = int(math.log2(1e100)/math.log2(5)) + 1
lg2 = math.log10(2)
lg3 = math.log10(3)
lg5 = math.log10(5)
count = 0
for i2 in range(n2):
    for i3 in range(n3):
        for i5 in range(n5):
            if lg2 * i2 + lg3 * i3 + lg5 * i5 <= 100:
                count += 1
print(count)

冬雪雪冬

加上break语句，用时1.4s
当i5循环大于100后就停止计算，同理i3的计算也在超过后停止，为什么i2不判断，大家想一下。

import math, time
st = time.time()
n2 = int(math.log2(1e100)) + 1
n3 = int(math.log2(1e100)/math.log2(3)) + 1
n5 = int(math.log2(1e100)/math.log2(5)) + 1
lg2 = math.log10(2)
lg3 = math.log10(3)
lg5 = math.log10(5)
count = 0
for i2 in range(n2):
    for i3 in range(n3):
        for i5 in range(n5):
            if lg2 * i2 + lg3 * i3 + lg5 * i5 <= 100:
                count += 1
            if lg2 * i2 + lg3 * i3 + lg5 * i5 > 100:
                break
        if lg2 * i2 + lg3 * i3 > 100:
            break
print(count)
print(time.time() - st)

小锟

# 观察前几个汉明数[1，2，3，4，5，6，8，9，10，12，15],
# 开始列表为1，然后增加了1*2 ， 1*3 ，2*2 ，1*5,2*3,，4*2，3*3
# 发现由前面的已知n项我们可以推出n+1项
# 5之前的质数有[2,3,5]
# 因此只用求出前n项中的元素与[2,3,5]的乘积取最小值就是第n+1项
# 用一个列表来记录位置



n = 10 ** 100
#只有第一项的汉明数
a = [1]
#判断最小值是否重复
chongfu = {1}
#记录位置的列表
nums = [0,0,0]

count = 1
while True :
    b = [a[nums[0]] * 2 , a[nums[1]] * 3 ,a[nums[2]] * 5]
    min_num = min(b)
    if min_num > n:break
    min_num_index = b.index(min_num)
    nums[min_num_index] += 1
    if min_num in chongfu:continue
    chongfu.add(min_num)
    a.append(min_num)
    count += 1
print(count)

老甲鱼与小甲鱼

嗯，那个我理解有点问题，不大于5的质数不是只有2,3,5吗，为什么可以组合出1,4这种数，数学不太好，百度定义太晦涩，求解

凤凰0620

import time
start =time.clock()

def get_hanmings(a=[]):
        start = 0
        c=[]
        b=[1,2,3,4,5]
        for i in b[start:]:
            for j in a[start:]:
                    c.append(i*j)       
        start +=  1
        return c

a=[1,2,3,4,5]
pre_result = [1,2,3,4,5]
while pre_result[-1]<=10**135:
    b = get_hanmings(a)
    a = list(set(b)-set(a))
    for i in a:
        pre_result.append(i)

result=[]
for i in pre_result:
    if i <= 10**100:
        result.append(i)

print(len(result))
end = time.clock()
print('Running time: %s Seconds'%(end-start))

最终版本，经过调整，while的范围在135左右，既能保证结果的完整，又能尽量节省时间
最后结果1697191个


在代码里加入了计时之后运行，平均运行成绩在12秒多

后记：我研究了一下规律，发现用差集进行迭代可以避免重复，结果实验了一下竟然超快的！！！！！！！！激动人心

凤凰0620

谢谢奖励，不过我后来修改了又~

hhhhhq

#可以算出2**332 < 10**100 < 2**333,3**209 < 10**100 < 3**210,5**143 < 10**100 < 5**144,且2*(3**209)>10**100

sum = 0
for a in range(0,333):
    x1 = 2**a
    for b in range(0,210):
        x2 = (3**b) * x1
        if x2 > 10**100:
            break
        for c in range(0,144):
            x3 = (5**c) * x2
            if x3 > 10**100:
                break
            sum += 1

print(sum)

#sb了，改一下。。答案是1697191

过客1993

a = b = c = 0
num_list = [1]
x = 10 ** 100
minnum = 0
while minnum < x:
    minnum = min(num_list[a] * 2, num_list[b] * 3, num_list[c] * 5)
    num_list.append(minnum)
    if minnum == num_list[a] * 2:
        a += 1
    if minnum == num_list[b] * 3:
        b += 1
    if minnum == num_list[c] * 5:
        c += 1

print len(num_list)

ps： python2.7
比速度，函数注释就一律不写了，主要原因是懒

qq910819

import datetime
def test(limit):
    a=0
    b=0
    c=0
    number=0
    count=0
    while number<=limit:
        while number<=limit:
            while number<=limit:
               
                count+=1
                c+=1
                number=(2**a)*(3**b)*(5**c)
            b+=1
            c=0
            number=(2**a)*(3**b)*(5**c)
        a+=1
        b=0
        number=(2**a)*(3**b)*(5**c)

    
    print(count)


a= datetime.datetime.now()
test(10**100)
b= datetime.datetime.now()
print("运行时间为：%s"%(b-a))

刚刚跟着小甲鱼学了一个多月python，还是菜鸟一只。先是写了一个遍历所有数字的方法，发现运行了半小时还是没有出结果。于是换了种思路，运行之后发现2s就出结果真的很激动。不过答案1697191是否正确真的也没有百分之百的把握，速度可能也不够快，总之重在参与。
借此机会谢谢小甲鱼和各位版主。

小Q学Python

m = 10**100
counts = 0

for i in range(1000):
    if 2**i > m:
        break
    for j in range(1000):
        if 3**j > m:
            break
        for k in range(1000):
            if 2**i*3**j*5**k > m:
                break
            counts += 1
            
print(counts)

%time %run qqq.py
1697191
Wall time: 3.32 s

意外惊喜sad

代码已修改

小剑剑

def binary_find_index(array,n,l=334):
    begin=0
    end=l-1
    while True:
        mid=(begin+end)//2
        if array[mid]<=n:
            if n<array[mid+1]:
                return mid
            begin=mid
        else:
            end=mid
            
x=1
fiveAndThree=[1]
for i in range(144):
    x*=5
    fiveAndThree.append(x)
two=[1]
x=1
for i in range(333):
    x=x<<1
    two.append(x)

result=0
for i in range(210):
    j=0
    while fiveAndThree[j]<=10**100:
        x=fiveAndThree[j]
        index=binary_find_index(two,x)
        if x<<(332-index)<=10**100:
            result+=333-index
        else:
            result+=332-index
        fiveAndThree[j]=x*3
        j+=1
        
print(result)

1697191

zhang1862899

number = []
for a in range(2,10**100):
    if a%2!=0 and a%3!=0 and a%5!=0:
        number.append(a)
count=0
for i in range(1,(10**100)+1):
    for b in number:
        if i%b==0:
            count+=1
            break
        
print('共有%d个汉明数' % (10**100-count))

算的太久了，很期待别人的答案，这是我挑选的时间最短的了

lalalaoh

def Ham(num):
    count = 0
    han_list=[]
    for each in range(num+1):
        han_list.append(0)
        if each==1 or each==2 or each==3 or each==5:
            count +=1
            han_list[each]=1
        elif each%2 == 0 and han_list[int(each/2)]: 
            count +=1
            han_list[each]=1
        elif each%3 ==0 and han_list[int(each/3)]: 
            count +=1
            han_list[each]=1
        elif each%5 ==0 and han_list[int(each/5)]: 
            count +=1
            han_list[each]=1
    return count

michaelol

高效版本
需要7秒找出10**100以内的汉明数
答案1697191个
代码如下

def hanmingshu(n):
    hanming=set()
    factor=[2,3,5]
    hanming_temp=set()
    hanming_tempnew=set()
    hanming_temp.add(1)
    hanming_tempmin=min(hanming_temp)
    if n==1:
        hanming.update(hanming_temp)
        return hanming
    else:
        hanming.update(hanming_temp)
        while(hanming_tempmin*2<=n):
            for i in hanming_temp:
                for j in factor:
                    if i*j<=n:
                        hanming_tempnew.add(i*j)
                    else:
                        break
            hanming.update(hanming_tempnew)
            hanming_temp.clear()
            hanming_temp.update(hanming_tempnew)
            hanming_tempmin=min(hanming_temp)
            hanming_tempnew.clear()
    return hanming

print(len(hanmingshu(10**100)))

gunjang

import time
from math import log,log2
def gethamming4_2(n):
        bmax = int(log(n,3))
        cmax = int(log(n,5))
        r = 0
        
        cp = 1
        for c in range(cmax+1):
                cbp = cp
                for b in range(int(log(n/cp,3))+1):
                        #2 loop times =[0..log2(n/cbp)]
                        r += 1 + int(log(n/cbp,2)) #1 include a==0
                        cbp *= 3
                cp *= 5
        return r

#Win7 x64+Python 3.62 x64 + AMD Phenom II X4 965 + DDR3*8G
st = time.time()
print(gethamming4_2(10**100)) #1697191
print(time.time()-st) ##4.2=0.016000747680664062

小冰冰偶哈哈

import math

#判断一个数是否是质数
def isprime(x):
        if x == 1:
            return False
        k = int(math.sqrt(x))
        for j in range(2,k+1):
            if x % j == 0:
                return False
        return True

def hamming(n):
    flag = True
    #质因子集合
    prime_list = list()
    #列出所有的质因子
    for i in range(2,n+1):
        if isprime(i) and n % i == 0:
            prime_list.append(i)
    prime_list = list(set(prime_list))
    #判断质因子是否小于等于5
    for j in prime_list:
        if j > 5:
            flag = False

    return flag
        
if __name__ == "__main__":
    number = int(input('请输入您需要的数字：'))
    hamming_list = []
    while number:
        result = hamming(number)
        if result:
            hamming_list.append(number)
            number -= 1
        else:
            number -= 1
    print(hamming_list)

算得很慢，持续优化中

小火木

def hmfun(n):
    data=1
    count=0
    i=0
    
    while data<n:
        j=0
        while data<n:
            k=0      
            while data<n:
                data=5**i*3**j*2**k
                if data<=n :
                    count+=1
                k+=1

            k=0
            data=5**i*3**j*2**k
            j+=1
          
        j=0
        data=5**i*3**j*2**k
        i+=1


    return count

if __name__=='__main__':
    print('10**100以内（包含10**100）共有%d个汉明数'% hmfun(10**100))