Кстати, можно подсчитать эту самую сумму для всех чисел от 1 до n за линейную сложность.
Надо использовать модифицированное решето Эратосфена, чтобы найти для каждого числа его минимальный простой делитель. Используя эти данные можно для каждого числа найти его минимальный простой делитель в максимальной степени, на которую число делится — один множитель из разложения на простые множители.
Далее, используя эти данные, можно подсчитать сумму всех простых делителей используя формулу S=(p1^(k1+1)-1)/(1-p1)*...*(pm^(km+1)-1)/(1-pm) (тут p1^k1...pm^km — разложение числа на простые множители).
Надо считать эту сумму делителей от меньших чисел к большим (обозначим ее S(n)). Тогда S(n) = S(n/p^k)*(p^k*p-1)/(p-1).
Но это так, для любопытных. Я думаю в вашей задаче достаточно для кадого числа проверять все делители до корня (а оставшиеся делители получаются как n/i, если i — делитель до корня). Надо только аккуратно разобрать случай, когда i = sqrt(n) — тогда второй делитель не надо рассматривать, ибо это вторая копия того же самого.
Онлайн калькулятор поможет вычислить сумму простых делителей числа, выпишет все делители, число положительных делителей натурального числа.
Сумма простых делителей числа |
|
| Число | |
|
|
|
Разделитель групп разрядов
Округлить до
Число прописью
Скачать калькулятор
Рейтинг: 3.2 (Голосов 22)
×
Пожалуйста напишите с чем связна такая низкая оценка:
×
Для установки калькулятора на iPhone — просто добавьте страницу
«На главный экран»
Для установки калькулятора на Android — просто добавьте страницу
«На главный экран»
Сообщить об ошибке
Смотрите также
| Неполное частное | Деление столбиком | Округление чисел | Количество разрядов в числе |
| Найти делимое | Все делители числа | Деление с остатком | Выгодность пиццы |
Сумма натуральных делителей (С) — величина, которая для каждого натурального числа показывает, чему равна сумма всех его натуральных делителей.
С точки зрения математики С является мультипликативной арифметической функцией: для любых натуральных и взаимно простых a и b справедливо свойство мультипликативности С(a • b) = С(a) • С(b).
Другая, похожая величина — это сумма S(n) собственных делителей числа, меньших чем исходное число n (число 1, являющееся делителем любого числа, входит в эту сумму). Она отличается от С(n) на величину самого числа n: S(n) = С(n) — n. Вычисление S позволяет разбить множество натуральных чисел на 3 группы: совершенные числа — натуральные числа, равные сумме своих меньших делителей; избыточные числа — для которых сумма S(n) больше числа; недостаточные числа — для которых сумма S(n) меньше числа.
Количество делителей для первых натуральных чисел:
| n | С(n) | S(n) |
|---|---|---|
| 1 | 1 | 0 (1 — недостаточное число) |
| 2 | 1 + 2 = 3 | 1 (2 — недостаточное число) |
| 3 | 1 + 3 = 4 | 1 (3 — недостаточное число) |
| 4 | 1 + 2 + 4 = 7 | 3 (4 — недостаточное число) |
| 5 | 1 + 5 = 6 | 1 (5 — недостаточное число) |
| 6 | 1 + 2 + 3 + 6 = 12 | 6 (6 — совершенное число) |
| 7 | 1 + 7 = 8 | 1 (7 — недостаточное число) |
| 8 | 1 + 2 + 4 + 8 = 15 | 7 (8 — недостаточное число) |
| 9 | 1 + 3 + 9 = 13 | 4 (9 — недостаточное число) |
| 10 | 1 + 2 + 5 + 10 = 18 | 8 (10 — недостаточное число) |
| 11 | 1 + 11 = 12 | 1 (11 — недостаточное число) |
| 12 | 1 + 2 + 3 + 4 + 6 + 12 = 28 | 16 (12 — избыточное число) |
| 13 | 1 + 13 = 14 | 16 (13 — недостаточное число) |
| 14 | 1 + 2 + 7 + 14 = 24 | 10 (14 — недостаточное число) |
| 15 | 1 + 3 + 5 + 15 = 24 | 9 (15 — недостаточное число) |
Свойства[]
- Если n ― простое число, то C(n) = n + 1
- Все простые и полупростые числа являются недостаточными
См. также[]
- Количество натуральных делителей
- Функция Мёбиуса
- Функция Эйлера
Improve Article
Save Article
Like Article
Improve Article
Save Article
Like Article
Given three integers A, B, C, the task is to find
ΣAi=1 ΣBj=1ΣCk=1 d(i.j.k), where d(x) is the number of divisors of x. Answer can be very large, So, print answer modulo 109+7.
Examples:
Input: A = 2, B = 2, c = 2
Output: 20
Explanation: d(1.1.1) = d(1) = 1;
d(1·1·2) = d(2) = 2;
d(1·2·1) = d(2) = 2;
d(1·2·2) = d(4) = 3;
d(2·1·1) = d(2) = 2;
d(2·1·2) = d(4) = 3;
d(2·2·1) = d(4) = 3;
d(2·2·2) = d(8) = 4.
Input: A = 5, B = 6, C = 7
Output: 1520
Approach:
- Find the number of divisors of all numbers in the range [1, N]
- Run three nested loops with iterators i, j, k starting from 1 to N
- Then find d(i.j.k) using pre computed number of divisors.
Below is the implementation of the above approach:
C++
#include <bits/stdc++.h>
using namespace std;
#define N 100005
#define mod 1000000007
int cnt[N];
void Divisors()
{
memset(cnt, 0, sizeof cnt);
for (int i = 1; i < N; i++) {
for (int j = 1; j * i < N; j++)
cnt[i * j]++;
}
}
int Sumofdivisors(int A, int B, int C)
{
int sum = 0;
Divisors();
for (int i = 1; i <= A; i++) {
for (int j = 1; j <= B; j++) {
for (int k = 1; k <= C; k++) {
int x = i * j * k;
sum += cnt[x];
if (sum >= mod)
sum -= mod;
}
}
}
return sum;
}
int main()
{
int A = 5, B = 6, C = 7;
cout << Sumofdivisors(A, B, C);
return 0;
}
Java
class GFG
{
static int N = 100005;
static int mod = 1000000007;
static int cnt[] = new int[N];
static void Divisors()
{
for (int i = 1; i < N; i++)
{
for (int j = 1; j * i < N; j++)
{
cnt[i * j]++;
}
}
}
static int Sumofdivisors(int A, int B, int C)
{
int sum = 0;
Divisors();
for (int i = 1; i <= A; i++)
{
for (int j = 1; j <= B; j++)
{
for (int k = 1; k <= C; k++)
{
int x = i * j * k;
sum += cnt[x];
if (sum >= mod)
{
sum -= mod;
}
}
}
}
return sum;
}
public static void main(String[] args)
{
int A = 5, B = 6, C = 7;
System.out.println(Sumofdivisors(A, B, C));
}
}
Python3
N = 100005
mod = 1000000007
cnt = [0] * N;
def Divisors() :
for i in range(1, N) :
for j in range(1, N // i) :
cnt[i * j] += 1;
def Sumofdivisors(A, B, C) :
sum = 0;
Divisors();
for i in range(1,A + 1) :
for j in range(1, B + 1) :
for k in range(1, C + 1) :
x = i * j * k;
sum += cnt[x];
if (sum >= mod) :
sum -= mod;
return sum;
if __name__ == "__main__" :
A = 5; B = 6; C = 7;
print(Sumofdivisors(A, B, C));
C#
using System;
class GFG
{
static int N = 100005;
static int mod = 1000000007;
static int []cnt = new int[N];
static void Divisors()
{
for (int i = 1; i < N; i++)
{
for (int j = 1; j * i < N; j++)
{
cnt[i * j]++;
}
}
}
static int Sumofdivisors(int A, int B, int C)
{
int sum = 0;
Divisors();
for (int i = 1; i <= A; i++)
{
for (int j = 1; j <= B; j++)
{
for (int k = 1; k <= C; k++)
{
int x = i * j * k;
sum += cnt[x];
if (sum >= mod)
{
sum -= mod;
}
}
}
}
return sum;
}
public static void Main(String[] args)
{
int A = 5, B = 6, C = 7;
Console.WriteLine(Sumofdivisors(A, B, C));
}
}
Javascript
<script>
let N = 100005;
let mod = 1000000007;
let cnt = new Array(N);
cnt.fill(0);
function Divisors()
{
for (let i = 1; i < N; i++)
{
for (let j = 1; j * i < N; j++)
{
cnt[i * j]++;
}
}
}
function Sumofdivisors(A, B, C)
{
let sum = 0;
Divisors();
for (let i = 1; i <= A; i++)
{
for (let j = 1; j <= B; j++)
{
for (let k = 1; k <= C; k++)
{
let x = i * j * k;
sum += cnt[x];
if (sum >= mod)
{
sum -= mod;
}
}
}
}
return sum;
}
let A = 5, B = 6, C = 7;
document.write(Sumofdivisors(A, B, C));
</script>
Time Complexity: O((A * B * C) + N3/2)
Auxiliary Space: O(N)
Last Updated :
08 Jun, 2022
Like Article
Save Article
Содержание материала
- Как определить количество делителей конкретного числа
- Видео
- Признаки делимости чисел
- Определение [ править
- Как найти число простых делителей числа
- Простые и составные числа
- Чем отличаются друг от друга, как найти
- Тест Миллера Рабина
Как определить количество делителей конкретного числа
Чтобы узнать, сколько положительных делителей у конкретного числа a, каноническое разложение которого выглядит как a = p 1 s 1 · p 2 s 2 · … · p n s n , нужно найти значение выражения ( s 1 + 1 ) · ( s 2 + 1 ) · … · ( s n + 1 ) . О количестве наборов переменных t 1 , t 2 , … , t n мы можем судить по величине записанного выражения.
Покажем на примере, как это вычисляется. Определим, сколько будет натуральных делителей у числа 3 900 , которое мы использовали в предыдущей задаче. Каноническое разложение мы уже записывали: 3 900 = 2 2 · 3 · 5 2 · 13 . Значит, s 1 = 2 , s 2 = 1 , s 3 = 2 , s 4 = 1 . Теперь подставим значения s 1 , s 2 , s 3 и s 4 в выражение ( s 1 + 1 ) · ( s 2 + 1 ) · ( s 3 + 1 ) · ( s 4 + 1 ) и вычислим его значение. Имеем ( 2 + 1 ) · ( 1 + 1 ) · ( 2 + 1 ) · ( 1 + 1 ) = 3 · 2 · 3 · 2 = 36 . Значит, это число имеет всего 36 делителей, являющихся натуральными числами. Пересчитаем то количество, что у нас получилось в предыдущей задаче, и убедимся в правильности решения. Если учесть и отрицательные делители, которых столько же, сколько и положительных, то получится, что у данного числа всего будет 72 делителя.
Условие: определите, сколько делителей имеет 84 .
Решение
Раскладываем число на множители.
84 42 21 7 1 2 2 3 7
Записываем каноническое разложение: 84 = 2 2 · 3 · 7 . Определяем, сколько у нас получится положительных делителей: ( 2 + 1 ) · ( 1 + 1 ) · ( 1 + 1 ) = 12 . Для учета отрицательных нужно умножить это число на 2 : 2 · 12 = 24 .
Ответ: всего у 84 будет 24 делителя – 12 положительных и 12 отрицательных.
Видео
Признаки делимости чисел
Признаки делимости чисел используются для того, чтобы ускорить процесс деления чисел. Существует множество признаков делимости и других интересных алгоритмов, значительно ускоряющих решение и освобождающих от излишней волокиты. Рассмотрим наиболее популярные из них.
Признак делимости на 10
Любое число, которое оканчивается нулем, делится без остатка на 10. Чтобы получить частное, достаточно отбросить цифру 0 в делимом.
Например, 380 : 10 = 38. Мы просто отбросили последний ноль в числе 380.
В случае, если мы имеем выражение такого вида 385 : 10, то получится 38 и 5 в остатке, поскольку 380 : 10 = 38, а пятерка это остаток, который не разделился.
Таким образом, если число оканчивается цифрой 0, то оно делится без остатка на 10. Если же оно оканчивается другой цифрой, то оно не делится без остатка на 10. Остаток в этом случае равен последней цифре числа. Действительно, в примере 385 : 10 = 38 (5 в остатке), остаток равен последней цифре в числе 385, то есть пятерке.
Признак делимости на 5 и на 2
Любое число, которое оканчивается нулем, делится без остатка и на 5, и на 2.
Примеры:
10 : 5 = 2
100 : 5 = 20
100 : 2 = 50
Признак делимости на 5
Если число оканчивается цифрой 0 или 5, то оно делится без остатка на 5.
Примеры:
355 : 5 = 71
200 : 5 = 40
475 : 5 = 95
Признак делимости на 3
Число делится на 3, если сумма цифр этого числа делится на 3. Например, рассмотрим число 27, сумма его цифр 2 + 7 = 9. Девять, как мы знаем делится на 3, значит и 27 делится на 3:
27 : 3 = 9
Признак делимости на 9
Число делится на 9, если сумма его цифр делится на 9. Например, рассмотрим число 18. Сумма его цифр 1 + 8 = 9. Девять делится на девять, значит и 18 делится на 9
18 : 9 = 2
Рассмотрим число 846. Сумма его цифр 8 + 4 + 6 = 18. Восемнадцать делится на девять, значит и 846 делится на 9:
Определение [ править
Функция «сумма положительных делителей »σx(n) для вещественного или комплексного числа x определяется как сумма x-х степеней положительных делителей числа n. Функцию можно выразить формулой
σ x ( n ) = ∑ d | n d x , <displaystyle sigma _(n)=sum _d^,!,> 
где d | n <displaystyle > 
означает «d делит n». Обозначения d(n), ν(n) и τ(n) (от немецкого Teiler = делитель) используются также для обозначения σ(n), или функции числа делителей [1] [2] . Если x равен 1, функция называется сигма-функцией или суммой делителей [3] , и индекс часто опускается, так что σ(n) эквивалентна σ1(n) [4] .
Аликвотная сумма s(n) для n — это сумма собственных делителей (то есть делители, за исключением самого n [5] , и равна σ1(n) − n. Аликвотная последовательность для n образуется последовательным вычислением аликвотной суммы, то есть каждое последующее значение в последовательности равно аликвотной сумме предыдущего значения.
Как найти число простых делителей числа
Если речь идет о целом малом числе, то решение такой задачи не представляет никакой сложности. Рассмотрим конкретный пример. Найдем простые делители числа 54.
Для этого:
- 54 делим на «два» и получаем 27;
- 27 нечетное, поэтому разделим его уже не на «два», а на следующее простое число, т. е. «три»;
- заметим, что 27=33;
- таким образом, разложение 54 имеет вид 54 = 21 * 33, т.е. простые делители числа 54 — это «два» и «три».
Однако это не все, что мы хотели знать. Теперь найдем число простых делителей числа 54. Оно равно произведению степеней простых множителей канонического разложения числа n = p1*d1 p2d2*⋅ …⋅*pmdm, увеличенных на 1. Иными словами, в общем случае K = (d1+1)*…* (dm+1).
Тогда для 54 имеем К = 2 * 4 = 8, т. е. общее число делителей равно восьми.
Обратите внимание, что все значительно упростилось, если бы речь шла о 23, 37, 103 и пр., так как каждый знает, сколько делителей у простого числа.
Простые и составные числа
Простым называется число, которое делится без остатка на единицу и на само себя. Другими словами, имеет только два делителя. Например, число 5 делится без остатка на единицу и на само себя:
5 : 1 = 5
5 : 5 = 1
Значит, число 5 является простым числом.
Составным же называется число, которое имеет два и более делителя. Например, число 4 составное, поскольку у него два и более делителя: 4, 2 и 1
4 : 4 = 1
4 : 2 = 2
4 : 1 = 4
Значит, число 4 является составным числом.
Чем отличаются друг от друга, как найти
Делитель отличается от кратного тем, что:
- делитель — это число, НА которое делится заданное число;
- кратное — это число, которое само ДЕЛИТСЯ НА заданное число.
Чтобы найти делители числа, нужно данное число разложить на множители.
Разложить на множители — представить число в виде произведения целых чисел.
Чтобы проверить, является ли одно число делителем другого, нужно разделить число на данное нам.
Для нахождения кратного числа заданному числу, нужно это число последовательно умножать на натуральные числа. Каждое полученное число будет кратно — будет делиться — заданному.
Делители и кратные связаны между собой. Например, делителем числа 15 является 3 и число, кратное 3, равно 15.
Тест Миллера Рабина
В криптографических целях часто используют именно этот вид определения простоты числа, который имеет несколько модификаций.
Тест Миллера—Рабина основан на проверке ряда условий, выполняемых для чисел, которые делятся только на 1 и на самих себя. Если хотя бы одно из требований нарушено, это «экзаменуемое» число признается составным.
Для данного m находятся целые нечетное число t и s, такие чтобы выполнялось условие m-1=2st.
Затем выбирается случайное число a, такое что 1<a<m. Если a не свидетельствует о простоте числа m, то программа должна выдать ответ «m составное» и завершить свою работу. В противном случае выбирается другое случайное число a и проверка повторяется снова. После того как будут установлены r свидетелей простоты, должен быть выдан ответ «m, вероятно, простое», и алгоритм завершит свою работу.
Следствием теоремы Рабина является тот факт, что если r чисел, которые выбраны случайно, признаны свидетелями для определения простоты числа m, то вероятность того, что оно составное, не может превосходить (4-r).
Теперь вы знаете, сколько делителей имеет простое число и как выяснить наиболее примитивный алгоритм вычисления НПД. Эти знания помогут вам в решении многих практических задач.