主页 / 问题 / 1530896
Accepted
Настя
Asked:2023-07-16 17:25:45 +0000 UTC2023-07-16 17:25:45 +0000 UTC

Python代码优化

  • 772

我为该任务编写了代码：

По заданному натуральному числу N необходимо вычислить количество 
натуральных чисел, которые есть делителями N! (факториала числа N).

Например, при N=4, N!=4·3·2·1=24. Это число имеет следующие делители: 
1, 2, 3, 4, 6, 8, 12, 24. Таким образом, искомое количество составляет 8.

Напишите программу, которая по натуральному N, находит количество 
делителей его факториала.

Формат входных данных

Единственная строка входного файла содержит одно целое число N (1≤N≤45).

Формат выходных данных

Единственная строка выходного файла должна содержать одно целое 
число –найденное количество делителей числа N!

Примеры
входные данные
4
выходные данные
8

входные данные 
3
выходные данные 
4

我的代码：

from math import factorial
a=int(input())
n=factorial(a)
ans=0 
q=1
while q*q<n:
    if n%q==0:
        ans+=2
    q+=1
if q*q==n:
    ans+=1
print(ans)

但在检查系统的一些测试中，代码运行时间过长，请帮忙优化一下！！！

python

2 个回答

  1. Best Answer

    想想看 - 对于阶乘的每个下一个值，n!不需要重新搜索一个巨大数字的所有因子，你只需要考虑以下 - n!= (n-1)!*n，并找出乘以如何n改变因子的数量。为此，将相对较小的值分解为简单的因子并将已经存在的素因子的度数n存储在例如字典中就足够了。

    因子总数的公式为：

    F = (P2+1)*(P3+1)*(P5+1)*(P7+1)*(P11+1)...*(Pq+1)

    其中Pk是素因数的次数k。

    例如5个！

     5! = 2^3 * 3 * 5
 Хранится  [3, 1, 1] или {2:3; 3:1; 5:1}
 F = 4 * 2 * 2 = 16

    6个！2 和 3 的幂加一，这样幂的列表（实际上是一本字典）就会像这样改变

     [4, 2, 1]) или  {2:4; 3:2; 5:1}

    答案将是

     F = 5 * 3 * 2 = 30

    我认为这些信息足以解决

    求素数幂的一个例子：

    from collections import Counter
def primes(n):
    res = Counter()
    d = 2
    while n > 1:
        m = 0   #степень множителя
        while n % d == 0:
            m += 1
            n //= d
        if m:
            res[d]  = m
        d += 2 if d > 2 else 1   #после двойки идём по нечётным
    return res

print(primes(840))

Counter({2: 3, 3: 1, 5: 1, 7: 1})

    让我再次提醒您，我们不是将这个函数应用于阶乘，而是应用于它的下一个因子，并且结果用于更新存储的素数幂。

    • 2

  2. 尝试一下：

    from math import factorial
n = factorial(int(input()))
sqrt = n**.5
ans = sqrt.is_integer()
sqrt = int(sqrt)
for i in range(2, sqrt):
    if n % i == 0:
        ans += 2
print(ans)
    • 0

相关问题