def Kelly2(n):
prod = 1
twos = 0
for i in range(2, n + 1):
while not i % 2:
i //= 2
twos += 1
while not i % 5:
i //= 5
twos -= 1
prod = prod * i % 10
return prod * pow(2, twos, 10) % 10
import math
from time import time
def just_factorial(n):
math.factorial(n)
return -1
def Shayan_original(n):
fact = math.factorial(n)
return str(fact).rstrip('0')[-1]
def Shayan_answer(n):
a = n // 5
b = n - 5 * a
fact_a = math.factorial(a)
fact_b = math.factorial(b)
power_a = 2 ** a
res = fact_a * fact_b * power_a
while (res % 10 == 0):
res //= 10
return int(res % 10)
def Seon(n):
lookup = [1, 1, 2, 6, 4, 2, 2, 4, 2, 8]
if n < 10:
return lookup[n]
if ((n // 10) % 10) % 2 == 0:
return (6 * Seon(n // 5) * lookup[n % 10]) % 10
else:
return (4 * Seon(n // 5) * lookup[n % 10]) % 10
def Kelly(n):
res = math.factorial(n)
while n:
n //= 5
res //= 10**n
return res % 10
def Kelly2(n):
prod = 1
twos = 0
for i in range(2, n + 1):
while not i % 2:
i //= 2
twos += 1
while not i % 5:
i //= 5
twos -= 1
prod = prod * i % 10
return prod * pow(2, twos, 10) % 10
funcs = just_factorial, Shayan_original, Shayan_answer, Seon, Kelly, Kelly2
# Correctness
for n in *range(1001), 65536:
expect = funcs[1](n)
for f in funcs[2:]:
result = str(f(n))
assert result == expect
# Speed
for f in funcs:
t = time()
f(65536)
print(f'{time() - t :8.6f} seconds ', f.__name__)
3条答案
按热度按时间tv6aics11#
有一个简洁的递归公式可以用途:设D(n)是n中最后一个非零数字!
参见this math stackexchange post以获得证明。
把它翻译成代码:
在我的笔记本电脑上,这个版本在5位数上的运行速度要快14,000倍。
5kgi1eie2#
一个简单的足够快的方法,只需计算阶乘,然后删除与素数因子5出现的频率一样多的零(因为这是导致零的原因,以及更频繁的素数因子2)。从1到n的每五个数字贡献一个素数因子5,这些数字中的每五个贡献另一个,等等。
以您的限额n=65536为基准:
我们看到,只计算阶乘,而不提取所需的数字,是很容易足够快。只是你原来通过字符串提取数字的速度很慢。
(Note:OP Shayan说他们的答案的解决方案 “对我有效,完成了工作” 而我的更快,这就是为什么我说我的足够快(也因为它对我来说远低于0.5秒)。看起来他们只是删除了他们的,因为他们无法解释。
另一个简单又快捷的方法:
这里我们自己把1到n的数相乘。但提取素因子2和5并分别计数。则n!= 2twos * 5fives * ProductOfReducedFactors。由于2和5的配对会导致不需要的尾随零,因此请计算我们有多少个2不能与5配对。我的代码就是这么做的。则nFactorialWithoutTrailingZeros = 2 twos * ProductOfReducedFactors。我们用
% 10
得到它的最后一位,我们可以在整个计算过程中使用它来保持ProductOfReducedFactors较小。测试代码(Attempt This Online!):
hc2pp10m3#
一个基于your answer的解决方案(只是重复你的还原步骤),一个击败Seon的优化版本,一个Seon的优化版本。n=65536的时间:
代码(Attempt This Online!):