我需要确定最小的数字基数系统,在该数字基数系统中表示的输入n(基数10)都是数字中的1.
例如: 基数为2的7等于111!答案是2
21 in base 2 is 10101 - contains 0, does not fit
21 in base 3 is 210 - contains 0 and 2, does not fit
21 in base 4 is 111 - contains only 1 it fits! answer is 4
n is always less than Number.MAX_SAFE_INTEGER or equivalent.
我有以下代码,可以很好地处理特定范围的数字,但对于大数字,该算法仍然很耗时:
def check_digits(number, base):
res = 1
while res == 1 and number:
res *= number % base
number //= base
return res
def get_min_base(number):
for i in range(2, int(number ** 0.5) + 2):
if check_digits(number, i) == 1:
return i
return number - 1
如何优化当前代码以使其运行得更快?