Делители факториала

Question

Делители факториала

По заданному натуральному числу N необходимо вычислить количество натуральных чисел, которые являются делителями N! (факториала числа N). Например, при N=4, N!=4⋅3⋅2⋅1=24. Это число имеет следующие делители: 1,2,3,4,6,8,12,24. Таким образом, искомое количество составляет 8. Напишите программу, которая по натуральному N находит количество делителей его факториала.

Ввод 4

Вывод 8

n = int(input())
d=1
factorial = 1
while n > 1:
    factorial *= n
    n -= 1
numb = factorial
count_of_dividers = 2
for i in range(numb - 1, 1, -1):
    if (numb % i == 0):
        count_of_dividers += 1
print(count_of_dividers)

Программа выполняется долго...

Answer 1

from math import factorial

# Функция факторизации, то есть разложения на простые множители
def factor(n):
    res = []
    i = 2
    while i * i <= n: # Ищем только до корня из n
        if n % i == 0:
            res.append(i)
            n //= i
        else:
            i += 1
    if n > 1:
        res.append(n)
    return res

n = int(input())
if n == 1: # Факторизация единицы ничего не даст, обработаем её отдельно
    print(1)
else:
    primes = factor(factorial(n)) # Рассчитываем факториал и получаем все простые делители
    # Наш ответ будем умножать в процессе, поэтому 1
    # num отвечает за количество повторений актуального простого делителя
    # последний обработанный простой делитель, начинаем с первого элемента
    answer, num, actual, length = 1, 1, primes[0], len(primes)
    for i in range(1, length): # Начинаем с 1, тк 0 элемент мы уже обработали
        if primes[i] == actual: # Если такой уже был, то просто увеличиваем счетчик
            num += 1
        else: # Если это новый простой делитель
            answer *= num + 1 # домножаем ответ на инкрементированное кол-во одинаковых делителей
            num = 1 # Обработка происходит уже на новом элементе, учитываем его
            actual = primes[i] # Меняем текущий элемент
    answer *= num + 1 # Последняя обработка не попадет в цикл, домножим так
    print(answer)

Answer 2

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

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

Пусть n = p₁^a₁ p₂^a₂ p₃^a₃ …, где p_i - различные простые, a_i - натуральные числа. Тогда число делителей n есть

σ₀(n) = (a₁ + 1)(a₂ + 1)(a₃ + 1)…

Подробнее в статье Функция делителей.
Разложение факториала в произведение простых строится без вычисления самого факториала.

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

a_i = ⌊ⁿ/_{p_i}⌋ + ⌊ⁿ/_{p_i²}⌋ + ⌊ⁿ/_{p_i³}⌋ + …

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

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

import math


def primes(n):
    sieve = [True] * n
    for i in range(2, math.isqrt(n - 1) + 1):
        if sieve[i]:
            for j in range(i * i, n, i):
                sieve[j] = False
    for i in range(2, n):
        if sieve[i]:
            yield i


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 primes(n + 1):
        p *= factorial_exponent(n, i) + 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 -p echo 10000 | python factorial-n-divisors.py
6440227747...0000000000
real 0.03
user 0.02
sys 0.00

Answer 3

'''
Задано натуральное число N, необходимо вычислить количество натуральных чисел, которые являются делителями факториала N. Для примера N=10.
'''

import os
import math
import time
from functools import lru_cache

@lru_cache(maxsize=None)
def prime_factors_count(n, p):
    count = 0
    while n > 0:
        n //= p
        count += n
    return count

def primes_up_to(n):
    sieve = [True] * (n + 1)
    sieve[0] = sieve[1] = False
    for start in range(2, int(math.sqrt(n)) + 1):
        if sieve[start]:
            for multiple in range(start*start, n + 1, start):
                sieve[multiple] = False
    return [num for num, is_prime in enumerate(sieve) if is_prime]

def count_divisors_of_factorial(n):
    primes = primes_up_to(n)
    divisors_count = 1
    for prime in primes:
        divisors_count *= (prime_factors_count(n, prime) + 1)
    return divisors_count

N = 10
start_time = time.time()
fact = math.factorial(N)
result = count_divisors_of_factorial(N)
end_time = time.time()
execution_time = end_time - start_time

print(f"Количество делителей факториала {N} равно {result}")
print(f"Время выполнения: {execution_time:.6f} секунд")

print("\nНажмите любую клавишу для продолжения...")
os.system("pause > nul" if os.name == "nt" else "read > /dev/null")

БЛОГ НА HUSL

Делители факториала

Ответы (3 шт):