蓝桥杯备战日志(Python)18-第几个幸运数字-(枚举只含某些因子的整数)

第几个幸运数字

原题

到 X 星球旅行的游客都被发给一个整数，作为游客编号。

X 星的国王有个怪癖，他只喜欢数字 3,5 和 7。

国王规定，游客的编号如果只含有因子：3,5,7就可以获得一份奖品。

我们来看前 10 个幸运数字是：

3 5 7 9 15 21 25 27 35 45

因而第 11 个幸运数字是： 49

小明领到了一个幸运数字 59084709587505，他去领奖的时候，人家要求他准确地说出这是第几个幸运数字，否则领不到奖品。

请你帮小明计算一下，59084709587505是第几个幸运数字。

分析

首先需要理解这里的“幸运数字”的含义：只能被1、3、5、7和数字本身整除的整数，1和数字本身可以忽略（所有整数都能被1和其本身整除）。题意需要求幸运数字n=59084709587505是第几个“幸运数字”，即求出n以内（包含n）有多少个“幸运数字”。

解题的关键点在于：根据因子3、5、7计算出“幸运数字”，然后统计数量，根据题意可以得到“幸运数字”可以用 3ⁱ * 5^j * 7^k (i,j,k = 0, 1, 2, 3, ... , 不取全0)表示。由于n是确定的，i, j, k的最大值是可以确定的，例如i，由3ⁱ<=n, 且i为整数可以得到i的最大值为int(log(n,3))。

源码

from math import log

count = 0
for i in range(int(log(n,3))+1):
    for j in range(int(log(n,5))+1):
        for k in range(int(log(n,7))+1):
            if 3**i * 5**j * 7**k <= n:
                count += 1
            else:
                break
print(count-1)  # 减1是因为上述统计了i,j,k同时取0的情况

上一篇：​​蓝桥杯备战日志(Python)17-激光样式&修剪灌木-(排列组合&画图找规律)​​