1

я написала код по задаче:

По заданному натуральному числу 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)

Но на некоторых тестах проверяющей системы код работает слишком долго, помогите пожалуйста его оптимизировать!!!

3 ответа 3

4

Подумайте вот о чём - для каждого очередного значения факториала 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! на единицу увеличиваются степени двойки и тройки, так что список (в реальности словарь) степеней изменится так

 [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})

Напомню ещё раз, что эту функцию применяем не к факториалу, а к его очередному сомножителю, а результат используется для обновления хранящихся степеней простых.

1

Быстрое решение строится на двух идеях.

  • Число делителей числа n можно вычислить по его разложению на простые множители.

    Пусть n = p1a1 p2a2 p3a3, где pi - различные простые, ai - натуральные числа. Тогда число делителей n есть

    σ0(n) = (a1 + 1)(a2 + 1)(a3 + 1)…

    Подробнее в статье Функция делителей.

  • Разложение факториала в произведение простых строится без вычисления самого факториала.

    Простое число pi входит в разложение факториала n! в степени

    ai = ⌊n / pi⌋ + ⌊n / pi2⌋ + ⌊n / pi3⌋ + …

    Доказывается непосредственно. Подробности в статье Факториал.

Рецепт решения: найти все простые числа pi: 1 ≤ pi ≤ n. Вычислить для них степени ai, добавить единицы, перемножить.

import math


def is_prime(n):
    return n >= 2 and all(n % d != 0 for d in range(2, n))


def factorial_exponent(n, p):
    # assuming prime p
    s = 0
    t = n // p
    while t > 0:
        s += t
        t //= p
    return s


def factorial_n_divisors(n):
    p = 1
    for i in range(n + 1):
        if is_prime(i):
            a = factorial_exponent(n, i)
            p *= a + 1
    return p


print(factorial_n_divisors(int(input())))
$ echo 3 | python factorial-n-divisors.py 
4

$ echo 4 | python factorial-n-divisors.py 
8

$ echo 45 | python factorial-n-divisors.py 
819624960

$ time echo 10000 | python factorial-n-divisors.py
6440227747...0000000000

real  0m0.506s
user  0m0.504s
sys   0m0.000s
0

Попробуйте это:

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)
1
  • 3 -> False, 4 -> 4 (должно быть 8). Это не работает. Commented 22 июл. 2023 в 11:30

Ваш ответ

Нажимая «Отправить ответ», вы соглашаетесь с условиями пользования и подтверждаете, что прочитали политику конфиденциальности.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.