A10. Делители числа.
Задание. Найдите сумму всех общих
натуральных делителей чисел 42, 56, 84.
Варианты ответов.
- 23;
- 9;
- 24;
- 26;
- 10.
Теория. здесь
Анализ. Не путать с понятием «наибольший общий делитель». Общим
делителем называется число, на которое делятся все числа, а наибольший общий
делитель – наибольшее из таких чисел, на которые делятся все числа.
Так же не путать с разложением на линейные множители.
Решение. Здесь мы будем раскладывать на простые множители, а затем
искать общие. Раскладываем числа на простые множители
Общие
делители: 2, 7, 14 и не забываем, что 1 является делителем любого числа,
поэтому он тоже общий!
Ответ. 3
Сумма натуральных делителей (С) — величина, которая для каждого натурального числа показывает, чему равна сумма всех его натуральных делителей.
С точки зрения математики С является мультипликативной арифметической функцией: для любых натуральных и взаимно простых 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
- Все простые и полупростые числа являются недостаточными
См. также[]
- Количество натуральных делителей
- Функция Мёбиуса
- Функция Эйлера
Given a natural number n, the task is to find sum of divisors of all the divisors of n.
Examples:
Input : n = 54 Output : 232 Divisors of 54 = 1, 2, 3, 6, 9, 18, 27, 54. Sum of divisors of 1, 2, 3, 6, 9, 18, 27, 54 are 1, 3, 4, 12, 13, 39, 40, 120 respectively. Sum of divisors of all the divisors of 54 = 1 + 3 + 4 + 12 + 13 + 39 + 40 + 120 = 232. Input : n = 10 Output : 28 Divisors of 10 are 1, 2, 5, 10 Sums of divisors of divisors are 1, 3, 6, 18. Overall sum = 1 + 3 + 6 + 18 = 28
Using the fact that any number n can be expressed as product of prime factors, n = p1k1 x p2k2 x … where p1, p2, … are prime numbers.
All the divisors of n can be expressed as p1a x p2b x …, where 0 <= a <= k1 and 0 <= b <= k2.
Now sum of divisors will be sum of all power of p1 – p10, p11,…., p1k1 multiplied by all power of p2 – p20, p21,…., p2k1
Sum of Divisor of n
= (p10 x p20) + (p11 x p20) +…..+ (p1k1 x p20) +….+ (p10 x p21) + (p11 x p21) +…..+ (p1k1 x p21) +……..+
(p10 x p2k2) + (p11 x p2k2) +……+ (p1k1 x p2k2).
= (p10 + p11 +…+ p1k1) x p20 + (p10 + p11 +…+ p1k1) x p21 +…….+ (p10 + p11 +…+ p1k1) x p2k2.
= (p10 + p11 +…+ p1k1) x (p20 + p21 +…+ p2k2).
Now, the divisors of any pa, for p as prime, are p0, p1,……, pa. And sum of divisors will be (p(a+1) – 1)/(p -1), let it define by f(p).
So, sum of divisors of all divisor will be,
= (f(p10) + f(p11) +…+ f(p1k1)) x (f(p20) + f(p21) +…+ f(p2k2)).
So, given a number n, by prime factorization we can find the sum of divisors of all the divisors. But in this problem we are given that n is product of element of array. So, find prime factorization of each element and by using the fact ab x ac = ab+c.
Below is the implementation of this approach:
C++
#include<bits/stdc++.h>
using namespace std;
int sumDivisorsOfDivisors(int n)
{
map<int, int> mp;
for (int j=2; j<=sqrt(n); j++)
{
int count = 0;
while (n%j == 0)
{
n /= j;
count++;
}
if (count)
mp[j] = count;
}
if (n != 1)
mp[n] = 1;
int ans = 1;
for (auto it : mp)
{
int pw = 1;
int sum = 0;
for (int i=it.second+1; i>=1; i--)
{
sum += (i*pw);
pw *= it.first;
}
ans *= sum;
}
return ans;
}
int main()
{
int n = 10;
cout << sumDivisorsOfDivisors(n);
return 0;
}
Java
import java.util.HashMap;
class GFG
{
public static int sumDivisorsOfDivisors(int n)
{
HashMap<Integer, Integer> mp = new HashMap<>();
for (int j = 2; j <= Math.sqrt(n); j++)
{
int count = 0;
while (n % j == 0)
{
n /= j;
count++;
}
if (count != 0)
mp.put(j, count);
}
if (n != 1)
mp.put(n, 1);
int ans = 1;
for (HashMap.Entry<Integer, Integer> entry : mp.entrySet())
{
int pw = 1;
int sum = 0;
for (int i = entry.getValue() + 1; i >= 1; i--)
{
sum += (i * pw);
pw *= entry.getKey();
}
ans *= sum;
}
return ans;
}
public static void main(String[] args)
{
int n = 10;
System.out.println(sumDivisorsOfDivisors(n));
}
}
Python3
import math as mt
def sumDivisorsOfDivisors(n):
mp = dict()
for j in range(2, mt.ceil(mt.sqrt(n))):
count = 0
while (n % j == 0):
n //= j
count += 1
if (count):
mp[j] = count
if (n != 1):
mp[n] = 1
ans = 1
for it in mp:
pw = 1
summ = 0
for i in range(mp[it] + 1, 0, -1):
summ += (i * pw)
pw *= it
ans *= summ
return ans
n = 10
print(sumDivisorsOfDivisors(n))
C#
using System;
using System.Collections.Generic;
class GFG
{
public static int sumDivisorsOfDivisors(int n)
{
Dictionary<int,
int> mp = new Dictionary<int,
int>();
for (int j = 2; j <= Math.Sqrt(n); j++)
{
int count = 0;
while (n % j == 0)
{
n /= j;
count++;
}
if (count != 0)
mp.Add(j, count);
}
if (n != 1)
mp.Add(n, 1);
int ans = 1;
foreach(KeyValuePair<int, int> entry in mp)
{
int pw = 1;
int sum = 0;
for (int i = entry.Value + 1;
i >= 1; i--)
{
sum += (i * pw);
pw = entry.Key;
}
ans *= sum;
}
return ans;
}
public static void Main(String[] args)
{
int n = 10;
Console.WriteLine(sumDivisorsOfDivisors(n));
}
}
Javascript
<script>
function sumDivisorsOfDivisors(n)
{
let mp = new Map();
for (let j = 2; j <= Math.sqrt(n); j++)
{
let count = 0;
while (n % j == 0)
{
n = Math.floor(n/j);
count++;
}
if (count != 0)
mp.set(j, count);
}
if (n != 1)
mp.set(n, 1);
let ans = 1;
for (let [key, value] of mp.entries())
{
let pw = 1;
let sum = 0;
for (let i = value + 1; i >= 1; i--)
{
sum += (i * pw);
pw = key;
}
ans *= sum;
}
return ans;
}
let n = 10;
document.write(sumDivisorsOfDivisors(n));
</script>
Output:
28
Time Complexity: O(√n log n)
Auxiliary Space: O(n)
Optimizations :
For the cases when there are multiple inputs for which we need find the value, we can use Sieve of Eratosthenes as discussed in this post.
This article is contributed by Aarti_Rathi and Anuj Chauhan. If you like GeeksforGeeks and would like to contribute, you can also write an article using write.geeksforgeeks.org or mail your article to review-team@geeksforgeeks.org. See your article appearing on the GeeksforGeeks main page and help other Geeks.
Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.
Last Updated :
23 Jun, 2022
Like Article
Save Article
Онлайн калькулятор поможет вычислить сумму простых делителей числа, выпишет все делители, число положительных делителей натурального числа.
Сумма простых делителей числа |
|
| Число | |
|
|
|
Разделитель групп разрядов
Округлить до
Число прописью
Скачать калькулятор
Рейтинг: 3.2 (Голосов 22)
×
Пожалуйста напишите с чем связна такая низкая оценка:
×
Для установки калькулятора на iPhone — просто добавьте страницу
«На главный экран»
Для установки калькулятора на Android — просто добавьте страницу
«На главный экран»
Сообщить об ошибке
Смотрите также
| Неполное частное | Деление столбиком | Округление чисел | Количество разрядов в числе |
| Найти делимое | Все делители числа | Деление с остатком | Выгодность пиццы |
1
Число и сумма натуральных делителей натурального числа.
2
Основная теорема арифметики. Всякое натуральное число п > 1 либо простое, либо может быть представлено, и притом единственным образом — с точностью до порядка следования сомножителей, в виде произведения простых чисел (можно считать, что любое натуральное число, большее 1, можно представить в виде произведения простых чисел, если считать, что это произведение может содержать всего лишь один множитель). Среди простых сомножителей, присутствующих в разложении n = p1*p2*…*pk, могут быть и одинаковые. Например, 24=2*2*2*3. Их можно объединить, воспользовавшись операцией возведения в степень. Кроме того, простые сомножители можно упорядочить по величине. В результате получается разложение
3
Такое представление числа называется каноническим разложением его на простые сомножители. Например, каноническое представление числа имеет вид 2520 = 23 З Из канонического разложения числа легко можно вывести следующую лемму: Если n имеет вид (1), то все делители этого числа имеют вид: (2)
4
В самом деле, очевидно, что всякое d вида (2) делит а. Пусть d делит а, тогда a=cd, где с некоторое натуральное число и, следовательно, все простые делители числа d входят в каноническое разложение числа а с показателями, не превышающими соответствующих показателей числа а. Рассмотрим две функции, заданные на множестве натуральных чисел: а) τ(n) — число всех натуральных делителей n; 2) σ(n) — сумма всех натуральных делителей числа n. Пусть n имеет каноническое разложение (1). Выведем формулы для числа и суммы его натуральных делителей.
5
Теорема 1. Число натуральных делителей числа n Доказательство. По лемме любой делитель имеет вид (2). При этом показатель β1 может принимать значения 0,1,2,…α1, то есть всего α1+1 значение (это соответствует делителям вида 1, р1, р1^2,…р1^α1) Аналогично, показатель β2 может принимать значения 0,1,2,…α2, то есть всего α2+1 значение (это соответствует делителям вида 1, р2, р2^2,…р2^α2) и т.д. Показатель βk может принимать значения 0,1,2,…αk, то есть всего αk+1 значение (это соответствует делителям вида 1, рk, рk^2,…рk^αk). Так как каждое из α1+1 значений, которые может принимать число β1, может сочетаться с любым из α2+1 возможных значений числа β2 и т. д., то мы видим, что общее число натуральных делителей числа n Пример. Число = 23 З имеет (3+1)(2+1)(1+1)(1+1) = 48 делителей.
6
Теорема 2. Пусть n имеет каноническое разложение (1). Тогда сумма натуральных делителей числа n равна Доказательство. Рассмотрим произведение Если раскрыть скобки, то получим сумму членов вида: (4)
7
Но такие члены являются делителями n, причем каждый делитель входит в сумму только один раз. Поэтому произведение (4′) равно сумме всех делителей n, т. е. равно σ(n). Итак, σ(n) можно вычислить по формуле (4). С другой стороны, каждая сумма 1+рm+ рm рmαm является суммой геометрической прогрессии с первым членом 1 и знаменателем рm.Поэтому иначе формулу (4) можно переписать так: (5) Пример. Найти сумму всех делителей числа =2 З2 5. Тогда σ(90)=[(22-1)/(2-1)] [З3-1)/(3-1)] [(52- 1)/(5-1)]=234 Формула (4) может помочь найти все делители числа.Так, например, чтобы найти все делители числа 90, раскроем скобки в следующем произведении (не производя операцию сложения): (1+2)(1+3+З2)(1+5)=(1+1*3+1*З2+1*2+2*3+2*З2)(1+5) = 1+3+З2+2+2*3+2*З2+ 5+3*5+З2*5+2*5+2*3*5+2*З2*5 = слагаемыми являются делители числа 90.
8
Задание. Найдите натуральное число, зная, что оно имеет только два простых делителя, что число всех делителей равно 6, а сумма всех делителей 28. Решение. Так как искомое число n имеет только два простых делителя, то оно представимо в виде n= р 1 α 1 р 2 α 2 (где будем считать, что р 1 < р 2 ). Так как число всех делителей этого числа равно 6, то по формуле (3) (α 1 +1)(α 2 +1)=6. Учитывая, что каждый из сомножителей в левой части не меньше 2 (α 1,α 2 1), а 6 представляется в виде произведения таких сомножителей единственным образом 6=23 с точностью до порядка следования множителей, то имеем два случая 1)
9
В данном случае (1+ р 1 + р 1 2 )(1+р 2 )=28, при этом 1+ р 1 + р 1 2 > 3, 1+р 2 >3. Откуда 1+ р 1 + р 1 2 =4, 1+р 2 =7 (эта система в натуральных числах решений не имеет) или 1+ р 1 + р 1 2 =7, 1+р 2 =4, откуда р 1 =2, р 2 =3 Отсюда n=2 2 3=12 Так как сумма всех делителей равна 28, то (1+р 1 )(1+ р 2 + р 2 2 )= раскладывается в произведение двух множителей следующими способами: 28=1*28=2*14=4*7 (с точностью до порядка следования множителей) Заметим, что 1 2, а значит, 1+р 1 >2, а 1+ р 2 + р 2 2 >7. Отсюда ни одно из разложений разложений числа 28 в произведение двух множителей нас не устраивает 2)
10
Задания для самостоятельной работы. 1. Найти все числа, имеющие ровно 2 простых делителя, всего 8 делителей, сумма которых равна Найти натуральные числа, которые делятся на 3 и на 4 и имеют ровно 21 натуральный делитель. 3. Найти наименьшее натуральное число, имеющее ровно 18 натуральных делителей. 4. Найти наименьшее число, кратное 5, имеющее 18 натуральных делителей. 5. Некоторое натуральное число имеет два простых делителя. Его квадрат имеет всего 15 делителей. Сколько делителей имеет куб этого числа? 6. Некоторое натуральное число имеет два простых делителя. Его квадрат имеет всего 81 делитель. Сколько делителей имеет куб этого числа? 7. Найти число вида m = 2x3y5z, зная, что половина его имеет на 30 делителей меньше, треть на 35 и пятая часть на 42 делителя меньше, чем само число.