Пусть N! = sum(a[i]), тогда (N + 1)! = (N + 1) * sum(a[i]). Причем так как a[i] делит N!, то (n + 1) * a[i] делит (N + 1)!. Таким образом, по разложению N! в сумму N делителей мы можем построить разложение (N + 1)! в сумму N делителей. Осталось как-то добавить один делитель.
Рассмотрим первые разложения:
3! = 3 + 2 + 14! = 12 + 8 + 3 + 15! = 60 + 40 + 15 + 4 + 1
Пусть минимальным делителем в разложении N будет 1, тогда в разложении (N + 1)! на N делителей минимальным будет N + 1. Причем его можно разбить на сумму N и 1, которые очевидно являются делителями (N + 1)! и при этом не встречаются в разложении до этого, так как меньше N + 1, который был минимальным.
Получаем следующий алгоритм:
N = 10
a = [3, 2, 1]
for n in range(3, N):
for i in range(n):
a[i] *= n + 1
a[i] -= 1
a.append(1)
print(a) #[1814400, 1209600, 453600, 120960, 25200, 4320, 630, 80, 9, 1]
# CHECK
from math import factorial
F = factorial(N)
print(sum(a) == F and len(a) == N and len(set(a)) == N and all(F % i == 0 for i in a)) #True
Improve Article
Save Article
Like Article
Improve Article
Save Article
Like Article
Given a number n, count the total number of divisors of n!.
Examples:
Input : n = 4
Output: 8
Explanation:
4! is 24. Divisors of 24 are 1, 2, 3, 4, 6,
8, 12 and 24.Input : n = 5
Output : 16
Explanation:
5! is 120. Divisors of 120 are 1, 2, 3, 4, 5, 6, 8, 10, 12, 15, 20, 24 30, 40, 60 and 12
A Simple Solution is to first compute the factorial of the given number, then count the number of divisors of the factorial. This solution is not efficient and may cause overflow due to factorial computation.
A better solution is based on Legendre’s formula. Below are the step:
- Find all prime numbers less than or equal to n (input number). We can use Sieve Algorithm for this. Let n be 6. All prime numbers less than 6 are {2, 3, 5}.
- For each prime number, p find the largest power of it that divides n!. We use Legendre’s formula for this purpose.
The value of largest power that divides n! is ⌊n/p⌋ + ⌊n/(p2)⌋ + ⌊n/(p3)⌋ + ……
Let these values be exp1, exp2, exp3,… Using the above formula, we get the below values for n = 6.- The largest power of 2 that divides 6!, exp1 = 4.
- The largest power of 3 that divides 6!, exp2 = 2.
- The largest power of 5 that divides 6!, exp3 = 1.
- The result is (exp1 + 1) * (exp2 + 1) * (exp3 + 1) … for all prime numbers, For n = 6, the values exp1, exp2, and exp3 are 4 2 and 1 respectively (computed in above step 2). So our result is (4 + 1)*(2 + 1) * (1 + 1) = 30
Below is the implementation of the above idea.
C++
#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long int ull;
vector<ull> allPrimes;
void sieve(int n)
{
vector<bool> prime(n+1, true);
for (int p=2; p*p<=n; p++)
{
if (prime[p] == true)
{
for (int i=p*2; i<=n; i += p)
prime[i] = false;
}
}
for (int p=2; p<=n; p++)
if (prime[p])
allPrimes.push_back(p);
}
ull factorialDivisors(ull n)
{
sieve(n);
ull result = 1;
for (int i=0; i < allPrimes.size(); i++)
{
ull p = allPrimes[i];
ull exp = 0;
while (p <= n)
{
exp = exp + (n/p);
p = p*allPrimes[i];
}
result = result*(exp+1);
}
return result;
}
int main()
{
cout << factorialDivisors(6);
return 0;
}
Java
import java.util.*;
class GFG
{
static Vector<Integer> allPrimes=new Vector<Integer>();
static void sieve(int n){
boolean []prime=new boolean[n+1];
for(int i=0;i<=n;i++)
prime[i]=true;
for (int p=2; p*p<=n; p++)
{
if (prime[p] == true)
{
for (int i=p*2; i<=n; i += p)
prime[i] = false;
}
}
for (int p=2; p<=n; p++)
if (prime[p])
allPrimes.add(p);
}
static long factorialDivisors(int n)
{
sieve(n);
long result = 1;
for (int i=0; i < allPrimes.size(); i++)
{
long p = allPrimes.get(i);
long exp = 0;
while (p <= n)
{
exp = exp + (n/p);
p = p*allPrimes.get(i);
}
result = result*(exp+1);
}
return result;
}
public static void main(String []args)
{
System.out.println(factorialDivisors(6));
}
}
Python3
allPrimes = [];
def sieve(n):
prime = [True] * (n + 1);
p = 2;
while(p * p <= n):
if (prime[p] == True):
i = p * 2;
while(i <= n):
prime[i] = False;
i += p;
p += 1;
for p in range(2, n + 1):
if (prime[p]):
allPrimes.append(p);
def factorialDivisors(n):
sieve(n);
result = 1;
for i in range(len(allPrimes)):
p = allPrimes[i];
exp = 0;
while (p <= n):
exp = exp + int(n / p);
p = p * allPrimes[i];
result = result * (exp + 1);
return result;
print(factorialDivisors(6));
C#
using System;
using System.Collections;
class GFG
{
static ArrayList allPrimes = new ArrayList();
static void sieve(int n)
{
bool[] prime = new bool[n+1];
for(int i = 0; i <= n; i++)
prime[i] = true;
for (int p = 2; p * p <= n; p++)
{
if (prime[p] == true)
{
for (int i = p*2; i <= n; i += p)
prime[i] = false;
}
}
for (int p = 2; p <= n; p++)
if (prime[p])
allPrimes.Add(p);
}
static int factorialDivisors(int n)
{
sieve(n);
int result = 1;
for (int i = 0; i < allPrimes.Count; i++)
{
int p = (int)allPrimes[i];
int exp = 0;
while (p <= n)
{
exp = exp + (n / p);
p = p * (int)allPrimes[i];
}
result = result * (exp + 1);
}
return result;
}
public static void Main()
{
Console.WriteLine(factorialDivisors(6));
}
}
PHP
<?php
$allPrimes = array();
function sieve($n)
{
global $allPrimes;
$prime = array_fill(0, $n + 1, true);
for ($p = 2; $p * $p <= $n; $p++)
{
if ($prime[$p] == true)
{
for ($i = $p * 2; $i <= $n; $i += $p)
$prime[$i] = false;
}
}
for ($p = 2; $p <= $n; $p++)
if ($prime[$p])
array_push($allPrimes, $p);
}
function factorialDivisors($n)
{
global $allPrimes;
sieve($n);
$result = 1;
for ($i = 0; $i < count($allPrimes); $i++)
{
$p = $allPrimes[$i];
$exp = 0;
while ($p <= $n)
{
$exp = $exp + (int)($n / $p);
$p = $p * $allPrimes[$i];
}
$result = $result * ($exp + 1);
}
return $result;
}
echo factorialDivisors(6);
?>
Javascript
<script>
let allPrimes = [];
function sieve(n)
{
let prime = new Array(n+1);
for(let i = 0; i <= n; i++)
prime[i] = true;
for (let p = 2; p * p <= n; p++)
{
if (prime[p] == true)
{
for (let i = p*2; i <= n; i += p)
prime[i] = false;
}
}
for (let p = 2; p <= n; p++)
if (prime[p])
allPrimes.push(p);
}
function factorialDivisors(n)
{
sieve(n);
let result = 1;
for (let i = 0; i < allPrimes.length; i++)
{
let p = allPrimes[i];
let exp = 0;
while (p <= n)
{
exp = exp + parseInt(n / p, 10);
p = p * allPrimes[i];
}
result = result * (exp + 1);
}
return result;
}
document.write(factorialDivisors(6));
</script>
Time Complexity: (O(n * log(logn))
Auxiliary Space: O(n)
This article is contributed by Shashank Mishra ( Gullu ). This article is reviewed by team GeeksforGeeks.
Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.
Last Updated :
13 Feb, 2023
Like Article
Save Article
Вот проблема, которую я недавно пытался решить: дано целое число n, каковы все его делители?
Делитель, также известный как фактор или множитель, — это такое целое число m, на которое n делится без остатка. Например, делителями числа 12 являются 1, 2, 3, 4, 6 и 12.
В итоге я написал кое-что с помощью itertools, и в моем коде используется несколько интересных моментов из теории чисел. Я не знаю, буду ли я возвращаться к нему снова, но я надумал написать эту статью, потому что мои попытки решить озвученный выше вопрос перетекли в довольно забавное упражнение.
Простейший подход
Если мы хотим найти все числа, которые делят n без остатка, мы можем просто перебрать числа от 1 до n:
def get_all_divisors_brute(n):
for i in range(1, int(n / 2) + 1):
if n % i == 0:
yield i
yield n
На деле нам нужно дойти только до n/2, потому что все, что больше этого значения, гарантировано не может быть делителем n — если вы разделите n на что-то большее, чем n/2, результат не будет целым числом.
Этот код очень прост, и для малых значений n он работает достаточно хорошо, но он довольно неэффективен и медлителен в других случаях. По мере увеличения n время выполнения линейно увеличивается. Можем ли мы сделать лучше?
Факторизация
В моем проекте я работал в основном с факториалами. Факториал числа n, обозначаемый n! — это произведение всех целых чисел от 1 до n включительно. Например:
8! = 8 × 7 × 6 × 5 × 4 × 3 × 2 × 1
Поскольку факториалы состоят преимущественно из небольших множителей, я решил попробовать получить список делителей, определив сначала наименьшие из них. В частности, я искал простые множители, то есть те, которые также являются простыми числами. (Простое число — это число, единственными делителями которого являются оно само и 1. Например, 2, 3 и 5 являются простыми, а 4 и 6 — нет).
Вот функция, которая находит простые делители числа n:
def get_prime_divisors(n):
i = 2
while i * i <= n:
if n % i == 0:
n /= i
yield i
else:
i += 1
if n > 1:
yield n
Это похоже на предыдущую функцию, использующую перебор делителей: мы продолжаем пробовать множители, и если находим подходящий, то делим на него. В противном случае мы проверяем следующее число. Это довольно стандартный подход к поиску простых множителей.
Теперь мы можем использовать этот метод для получения факторизации числа, то есть для его записи в виде произведения простых чисел. Например, факторизация числа 8! выглядит следующим образом:
8! = 2^7 × 3^2 × 5 × 7
Вычисление такой факторизации относительно эффективно, особенно для факториалов, так как, поскольку все простые множители очень малы, вам не нужно делать много делений.
В теории чисел есть утверждение, называемое основной теоремой арифметики, которое гласит, что простые факторизации (разложения) уникальны: для любого числа n существует только один способ представить его в виде произведения простых множителей. (Я не буду приводить здесь доказательство, но вы можете найти его в Википедии).
Это дает нам способ находить делители путем перебора всех комбинаций простых множителей. Простые множители любого m делителя числа n должны входить в подмножество простых множителей n, иначе m не делило бы число n.
Переход от факторизации к делителям
Для начала разложим исходное число на простые множители с указанием «кратности», то есть мы должны получить список всех множителей и количество раз, которое каждый из них встречается в факторизации:
import collections
def get_all_divisors(n):
primes = get_prime_divisors(n)
primes_counted = collections.Counter(primes)
...
Затем, давайте продолжим и возведем каждое простое число во все степени, которые могут появиться в возможном делителе n.
def get_all_divisors(n):
...
divisors_exponentiated = [
[div ** i for i in range(count + 1)]
for div, count in primes_counted.items()
]
Например, для 8! представленный код выдаст нам следующее:
[
[1, 2, 4, 8, 16, 32, 64, 128], // 2^0, 2^1, ..., 2^7
[1, 3, 9], // 3^0, 3^1, 3^2
[1, 5],
[1, 7],
]
Затем, чтобы получить делители, мы можем использовать довольно удобную функцию itertools.product, которая принимает на вход итерабельные объекты и возвращает все возможные упорядоченные комбинации их элементов. В нашем случае она выбирает по одному числу из каждого списка с возведениями в степень, а затем, перемножая их вместе, мы получаем очередной делитель n.
import itertools
def calc_product(iterable):
acc = 1
for i in iterable:
acc *= i
return acc
def get_all_divisors(n):
...
for prime_exp_combination in itertools.product(*divisors_exponentiated):
yield calc_product(prime_exp_combination)
Таким образом, мы находим все делители n (хотя, в отличие от предыдущих функций, они не отсортированы).
Собираем все вместе
Сложив все это, мы получим следующую функцию для вычисления делителей n:
import collections
import itertools
def get_prime_divisors(n):
i = 2
while i * i <= n:
if n % i == 0:
n /= i
yield i
else:
i += 1
if n > 1:
yield n
def calc_product(iterable):
acc = 1
for i in iterable:
acc *= i
return acc
def get_all_divisors(n):
primes = get_prime_divisors(n)
primes_counted = collections.Counter(primes)
divisors_exponentiated = [
[div ** i for i in range(count + 1)]
for div, count in primes_counted.items()
]
for prime_exp_combination in itertools.product(*divisors_exponentiated):
yield calc_product(prime_exp_combination)
print(list(get_all_divisors(40320))) # 8!
Такая реализация очень эффективна, особенно когда у вас много маленьких простых множителей, как в случае с факториалами, с которыми я работал. Я не знаю, насколько хорошо она покажет себя в общем случае, и, если вы занимаетесь серьезными научными вычислениями, я уверен, что вы легко найдете уже реализованные и оптимизированные алгоритмы для такого рода вещей.
Часто в олимпиадных задачах, чтобы оценить асимптотику алгоритма, требуется знать примерное число делителей поступающего на вход числа. Точнее, требуется знать максимальное число делителей среди всех чисел до, скажем, миллиарда.
Самая грубая оценка — O (sqrt(N)), а именно, не более двух квадратных корней из N.
Но часто это оказывается слишком грубой оценкой, неоправданно завышенной.
Обычная используемая мной оценка — O(кубического корня из N). Эту таинственную оценку я услышал когда-то давно от кого-то, и никогда её не понимал, но пользовался ей, и она работала.
Совсем недавно мы делали стресс-тест, и на числах до миллиарда она подтвердилась — число делителей не превосходит двух кубических корней из числа. Этого «доказательства» вполне достаточно, чтобы и дальше применять эту оценку на практике. Но найти ей математическое объяснение ну никак не получалось.
Сегодня в очередной раз решил поискать на эту тему в интернете. На этот раз нашёл то. что нужно, на удивление быстро: en.wikipedia.org/wiki/Divisor_function. Здесь много всякого интересного, но вот главная вещь, поразительная для меня формула:
«для любого eps>0 выполняется: d(n) = o(n^eps)»
Выходит, на самом деле число делителей ведёт себя на бесконечности не только лучше квадратного, кубического и прочего корней из числа n; оно вообще является субполиномиальной величиной!
Другие оценки:
- Wigert: «d(n) ~ n ^ (log2 / log log n)» (ну я примерно передал порядок, на самом деле там формула посложнее)
- Дирихле: «СУММА_{i=1..n} d(i) / n ~ log n + 2 gamma — 1»
P.S. Некоторым это может показаться бояном, но я знаю, что многие до сих пор даже не знают, что число делителей меньше квадратного корня, не говоря уже о таких «крутых» оценках 
P.P.S. Для олимпиад, где обычно в таких задачах мы имеем дело с числами до 10^9 — 10^12, эти оценки малополезны (здесь надо по-прежнему брать корень кубический), но они интересны чисто как математический факт.
Сообщение было отмечено ZX Spectrum-128 как решение
Решение
Hitoku, похвальный оптимизм. 45!, надо же… Задачка не такая простая, как я выгляжу.
| Тип | Число бит,
без знакового бита |
Поместится |
| ShortInt | 7 | 5! |
| Byte | 8 | 5! |
| SmallInt,
Integer (TP) |
15 | 7! |
| Word | 16 | 8! |
| Integer,
LongInt |
31 | 12! |
| Cardinal,
Longword |
32 | 12! |
| Int64 | 63 | 20! |
| UInt64,
QWord |
64 | 20! |
Задача не решена. Сами делители искать никто не просит, поэтому можно поступить так:
— случаи 0! и 1! рассматривать отдельно;
— количество очевидных делителей n, то есть все сомножители факториала;
— далее находим все простые числа, меньшие n, и кратность их вхождения в факториал по формуле
где
— скобки обозначают округление в сторону меньшего целого (можно использовать trunc);
— k — количество раз, которое данное простое число p делит n!;
— i — степени числа p, такие, что pi ≤ n (инкрементируем i и вычисляем k до тех пор, пока очередное trunc(n/pi) > 0).
Другие простые числа, кроме найденных, n! не делят.
Получив все простые делители n! и их кратность, находим остальные делители факториала, а именно, все составные числа, бóльшие n, вооружившись тем, что конкретное составное число возможно представить в виде произведения простых чисел единственным способом. Это можно сделать, составляя числа из комбинаций произведений найденных простых делителей с учётом их кратности, выбирая те произведения, которые > n. Кстати, сами эти простые делители уже учтены, их количество к общему количеству делителей добавлять не следует.
К примеру, для того же 4! имеем (формулы не использую, и так всё ясно):
— очевидные делители: 1, 2, 3, 4.
— простые делители: 2, кратность 3 (то есть, 4! можно поделить на 2 трижды) и 3, кратность 1.
перебираем:
2*2=4 =4 — не подходит
2*2*2=8 >4 — подходит
2*3=6 >4 — подходит
2*2*3=12 >4 — подходит
2*2*2*3=24 >4 — подходит.
Всё, перебрали все комбинации простых делителей с учётом их кратности.
Получили 4 очевидных делителя и 4 делителя, бóльших n. Всего 8, как и планировалось.
Естественно, произведение простых чисел до конца вычислять не нужно, нужно только убедиться, что это произведение > n.
Таким образом, максимальное число, которое может получиться в программе, будет меньше n*pmax. Иными словами, максимум будет n2, если pmax=n, что куда как меньше, чем n!. И при использовании переменных типа integer программа сможет подсчитать делители вплоть до 46340!.
Добавлено через 1 час 36 минут
Хотя… Задачку можно решить и «более в лоб», да ещё и оптимальнее: получить простые делители (и, кстати, никак далее их и не использовать) и их кратности, и подсчитать количество уникальных комбинаций из произведения делителей с учётом их кратностей, причём для каждого простого делителя соответствующее ему k считать от 0 до kmax, и вычислить количество делителей как
Причём будет учтён и делитель 1.
Для 4! получается: (3+1)(1+1)=8
Добавлено через 12 часов 8 минут
Ох, нет… Что-то я немножко не прав… Количество делителей для каждого простого делителя перемножаются, поэтому количество делителей 46! уже не влезает в тип integer… Вот откуда это с виду несуразное «до 45» взялось…
До 45 простых чисел не так много, поэтому проще использовать таблицу простых чисел:
| Pascal | ||
|
Если всё же будет нужно определять простоту делителя, тогда, к примеру, так:
| Pascal | ||
|
Функция определения простоты числа взята отсюда: Алгоритм, который устанавливает – является ли число простым. В принципе, эта функция даёт выигрыш при достаточно больших числах, поэтому функцию IsPrime можно применить какую-нибудь попроще, например:
| Pascal | ||
|
1