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
Здравствуйте, дорогие читатели! Как посчитать, сколько делителей у какого-нибудь числа? Если это число маленькое, то никаких сложностей не возникает. Например, для числа 10, мы легко можем найти все делители и посчитать их количество простым перебором. А вот как узнать, на какое количество различных чисел делится, например, число 720? Можно, конечно, опять же перебрать все делители, но это будет довольно трудоемко. При чем, 720 – еще и довольно маленькое число.
Сегодня, я Вам расскажу, как находить количество делителей любого натурального числа, зная всего лишь одну простую формулу.
На самом деле, наша сегодняшняя формула будет даже проще, чем те, которые изображены на картинке выше)
Вы находитесь на канале Trifler, где я разбираю интересные математические задачи, а также рассуждаю на некоторые околоматематические темы. Если Вы искренне увлечены математикой, но еще не подписаны на этот канал, то самое время это исправить! Подписаться
Чудо-формула
Ну что ж, пора переходить от разговоров к делу.
Мы знаем, что любое натуральное число можно представить в виде произведения простых чисел, которые являются его делителями. Так как один и тот же простой делитель может встречаться несколько раз, то любое натуральное числа можно записать так:
Если не совсем понятно, о чем идет речь, то потом посмотрите пример ниже. На самом деле, все очень просто.
Так вот, после того, как мы найдем такое представление числа n, количество его делителей можно будет посчитать по формуле:
Посмотрим, как все это считается на примере
Пример
Раскладываем это число на простые множители, чтобы получить нужное представление:
Теперь, запишем число 720 в каноническом виде:
Ну и все, остается только применить чудо-формулу:
Вот и все, получили, что у числа 720 имеется 30 различных натуральных делителей. Стоит сделать замечание:
По этой формуле мы считаем количество делителей вместе с единицей и самим числом.
Если Вам понравилась статья, то обязательно ставьте лайки и комментируйте ее. Это поспособствует тому, чтобы ее увидело много людей!
Читайте также ТОП-3 статьи, выпущенные в этом месяце на моем канале:
- Quincy: робот, который обучит Ваших детей математике, английскому и рисованию
- Почему вторая степень это квадрат, а третья – куб
- Необычное тригонометрическое уравнение
Граф делителей факториала
31.12.2019Математика
Учитывая число n , подсчитайте общее количество делителей n! ,
Примеры:
Input : n = 4 Output: 24 4! is 24. Divisors of 24 are 1, 2, 3, 4, 6, 8, 12 and 24. Input : n = 5 Output : 16 5! is 120. Divisors of 120 are 1, 2, 3, 4, 5, 6, 8, 10, 12, 15, 20, 24 30, 40, 60 and 120 Input : n = 6 Output : 30
Простое решение состоит в том, чтобы сначала вычислить факториал данного числа, а затем подсчитать делители числа факториала. Это решение неэффективно и может вызвать переполнение из-за факторных вычислений.
Лучшее решение основано на формуле Лежандра . Ниже приведены шаги.
- Найти все простые числа, меньшие или равные n (входное число). Мы можем использовать алгоритм сита для этого. Пусть n равно 6. Все простые числа меньше 6 равны {2, 3, 5}.
- Для каждого простого числа p найдите его наибольшую степень, которая делит n !. Мы используем ниже формулу формулы Лежандра для этой цели.
Величина наибольшей степени, которая делит p, равна ⌊n / p⌋ + ⌊n / (p 2 ) ⌋ + ⌊n / (p 3 ) ⌋ + ……
Пусть эти значения будут exp1, exp2, exp3, .. Используя приведенную выше формулу, мы получим значения ниже для n = 6.- Наибольшая степень 2, которая делит 6 !, exp1 = 4.
- Наибольшая степень 3, которая делит 6 !, exp2 = 2.
- Наибольшая степень 5, которая делит 6 !, exp3 = 1.
- Результат равен (exp1 + 1) * (exp2 + 1) * (exp3 + 1)… для всех простых чисел. Для n = 6 значения exp1, exp2 и exp3 равны 4 2 и 1 соответственно (вычисляются на предыдущем шаге 2). Таким образом, наш результат (4 + 1) * (2 + 1) * (1 + 1) = 30
Ниже приведена реализация вышеуказанной идеи.
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;
}
Джава
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);
?>
Выход:
30
Эта статья предоставлена Шашанком Мишрой (Гуллу). Эта статья рецензируется командой GeeksforGeeks.
Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.
Рекомендуемые посты:
- Сумма делителей факториала числа
- Считать цифры в факториале | Комплект 1
- Считать цифры в факториале | Набор 2
- Подсчитать факторные числа в заданном диапазоне
- Подсчет делителей n в O (n ^ 1/3)
- Подсчет конечных нулей в факториале числа
- Проверьте, является ли количество делителей четным или нечетным
- Подсчитайте делители n, которые имеют хотя бы одну общую цифру с n
- C Программа для проверки, является ли число делителей четным или нечетным
- Подсчет делителей массива умножения
- Подсчитайте суммарные делители A или B в заданном диапазоне
- Посчитайте все совершенные делители числа
- Количество чисел ниже N, сумма простых делителей которых равна K
- Подсчитать количество целых чисел меньше или равно N, который имеет ровно 9 делителей
- Количество делителей, имеющих больше установленных битов, чем частное при делении N
Граф делителей факториала
0.00 (0%) 0 votes
Часто в олимпиадных задачах, чтобы оценить асимптотику алгоритма, требуется знать примерное число делителей поступающего на вход числа. Точнее, требуется знать максимальное число делителей среди всех чисел до, скажем, миллиарда.
Самая грубая оценка – 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, эти оценки малополезны (здесь надо по-прежнему брать корень кубический), но они интересны чисто как математический факт.
Вот проблема, которую я недавно пытался решить: дано целое число 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!
Такая реализация очень эффективна, особенно когда у вас много маленьких простых множителей, как в случае с факториалами, с которыми я работал. Я не знаю, насколько хорошо она покажет себя в общем случае, и, если вы занимаетесь серьезными научными вычислениями, я уверен, что вы легко найдете уже реализованные и оптимизированные алгоритмы для такого рода вещей.
