Как найти число по сумме его делителей

Как найти число по сумме его делителей

Правила форума

В этом разделе нельзя создавать новые темы.

Если Вы хотите задать новый вопрос, то не дописывайте

его в существующую тему, а создайте новую в корневом разделе “Помогите решить/разобраться (М)”.

Если Вы зададите новый вопрос в существующей теме, то в случае нарушения оформления или других правил форума Ваше сообщение и все ответы на него могут быть удалены без предупреждения.

Не ищите на этом форуме халяву

, правила запрещают участникам публиковать готовые решения стандартных учебных задач. Автор вопроса обязан привести свои попытки решения

и указать конкретные затруднения.

Обязательно просмотрите тему

Правила данного раздела, иначе Ваша тема может быть удалена

или перемещена в Карантин, а Вы так и не узнаете, почему.

 

 Найти число по количеству делителей и их сумме

Сообщение15.04.2011, 23:51 

Аватара пользователя


24/03/09
43
Питер

Всем привет.
Друзья, попала мне вот такая вот, казалось бы, не сложная задачка:

Нам известно, что у числа $n$ $6$ делителей. (Включая $1$ и само число $n$). Чему равно это $n$, если сумма делителей равно $126$?

P.S. Нашел в интернете похожую задачку. Условие такое же, только сумма равна $124$. В таком случае подходит число 75, ведь: $1+75+15+5+25+3=124$
Возможно в моем условии очепятка и там должно стоять число 124?
Но как доказать в случае 124=>75 я тоже не очень понял.

Благодарю за помощь!

Профиль  

ИСН 

 Re: Делители

Сообщение16.04.2011, 00:16 
Заслуженный участник
Аватара пользователя


18/05/06
13415
с Территории

Такое число (которое даёт 126) тоже есть, а находится оно длительной вознёй с разложением на простые.
Или уж перебором.

Профиль  

svv 

 Re: Делители

Сообщение16.04.2011, 00:36 
Заслуженный участник


23/07/08
10059
Crna Gora

Нашел простой способ.

Пусть разложение $n$ на простые множители имеет вид $n=ab$. Тогда $n$ имеет $4$ делителя: $1$, $a$, $b$, $ab=n$. Мало что-то у нас делителей, по условию должно быть $6$.

Прибавим ещё один простой множитель. Теперь $n=abc$. Тогда $n$ имеет аж $8$ делителей: $1$, $a$, $b$, $c$, $ab$, $ac$, $bc$, $abc=n$. Перебор.

Где же выход? А он есть. :-)

Профиль  

bot 

 Re: Делители

Сообщение16.04.2011, 05:55 
Заслуженный участник
Аватара пользователя


21/12/05
5844
Новосибирск

Число и сумма делителей
Разложение в произведение простых может быть Либо $n=p^5$ либо $n=pq^2$.
Первый случай отпадает сразу (p=2 – сумма недолетает, p=3 – перелетает), со вторым тоже разговор короткий: $q=2, 3, 5$. Решений нет.

— Сб апр 16, 2011 10:03:02 —

Упс, 126 ведь на 7 делится – ИСН

прав, решение есть.

Профиль  

VAL 

Re: Делители

Сообщение16.04.2011, 08:05 
Заслуженный участник


27/06/08
4051
Волгоград

Такое число (которое даёт 126) тоже есть, а находится оно длительной вознёй с разложением на простые.
Или уж перебором.

Зачем, зря пугаете? 30 секунд (этого вполне достаточно для полного обоснованного решения задачи) – это длительная возня?

PS: Разумеется, подход тот же, что у bot

‘а.
1) $n=pq^2 (n=p^5$ не подходит);
2) $126=(p+1)(q^2+q+1)$
И первое же $q$ дает ответ.

Профиль  

Модераторы: Модераторы Математики, Супермодераторы

Источник

Здравствуйте, дорогие читатели! Как посчитать, сколько делителей у какого-нибудь числа? Если это число маленькое, то никаких сложностей не возникает. Например, для числа 10, мы легко можем найти все делители и посчитать их количество простым перебором. А вот как узнать, на какое количество различных чисел делится, например, число 720? Можно, конечно, опять же перебрать все делители, но это будет довольно трудоемко. При чем, 720 – еще и довольно маленькое число.

Сегодня, я Вам расскажу, как находить количество делителей любого натурального числа, зная всего лишь одну простую формулу.

Как легко найти количество натуральных делителей любого числа

На самом деле, наша сегодняшняя формула будет даже проще, чем те, которые изображены на картинке выше)

Вы находитесь на канале Trifler, где я разбираю интересные математические задачи, а также рассуждаю на некоторые околоматематические темы. Если Вы искренне увлечены математикой, но еще не подписаны на этот канал, то самое время это исправить! Подписаться

Чудо-формула

Ну что ж, пора переходить от разговоров к делу.

Мы знаем, что любое натуральное число можно представить в виде произведения простых чисел, которые являются его делителями. Так как один и тот же простой делитель может встречаться несколько раз, то любое натуральное числа можно записать так:

Как легко найти количество натуральных делителей любого числа

Если не совсем понятно, о чем идет речь, то потом посмотрите пример ниже. На самом деле, все очень просто.

Так вот, после того, как мы найдем такое представление числа n, количество его делителей можно будет посчитать по формуле:

Как легко найти количество натуральных делителей любого числа

Посмотрим, как все это считается на примере

Пример

Как легко найти количество натуральных делителей любого числа

Раскладываем это число на простые множители, чтобы получить нужное представление:

Как легко найти количество натуральных делителей любого числа

Теперь, запишем число 720 в каноническом виде:

Как легко найти количество натуральных делителей любого числа

Ну и все, остается только применить чудо-формулу:

Как легко найти количество натуральных делителей любого числа

Вот и все, получили, что у числа 720 имеется 30 различных натуральных делителей. Стоит сделать замечание:

По этой формуле мы считаем количество делителей вместе с единицей и самим числом.

Если Вам понравилась статья, то обязательно ставьте лайки и комментируйте ее. Это поспособствует тому, чтобы ее увидело много людей!

Читайте также ТОП-3 статьи, выпущенные в этом месяце на моем канале:

  1. Quincy: робот, который обучит Ваших детей математике, английскому и рисованию
  2. Почему вторая степень это квадрат, а третья – куб
  3. Необычное тригонометрическое уравнение
Источник

gray621

36 / 51 / 11

Регистрация: 14.01.2021

Сообщений: 406

1

Найти число по количеству делителей

17.01.2021, 19:52. Показов 9251. Ответов 14

Метки python 3, питон (Все метки)

Студворк — интернет-сервис помощи студентам

Формат ввода
Вводится натуральное число – количество делителей, считая единицу и само число.

Формат вывода
Вывести наименьшее число с таким количеством делителей.

Пример 1
Ввод Вывод
8
24
Пример 2
Ввод Вывод
48
2520
Примечания
При решении нельзя использовать функции и методы, а также списки и словари.

Вот код, чтобы найти кол-во делителей числа, а как наоборот?

Python 
1
2
3
4
5
6
7
8
9
10

n = int(input())
count_of_dividers = 0
 
for i in range(n - 1, 1, -1):
 
    if n % i == 0:
 
        count_of_dividers += 1
 
print(count_of_dividers)



0

unfindable_404

Эксперт Python

690 / 473 / 204

Регистрация: 22.03.2020

Сообщений: 1,052

17.01.2021, 20:32

2

На основе вашего кода:

Python 
1
2
3
4
5
6
7
8
9
10
11

divs = int(input())
n = 1
while True:
    count_of_dividers = 0
    for i in range(n, 0, -1):
        if n % i == 0:
            count_of_dividers += 1
    if count_of_dividers == divs:
        print(n)
        break
    n += 1



1

Эксперт Python

7250 / 4039 / 1779

Регистрация: 27.03.2020

Сообщений: 6,865

17.01.2021, 20:42

3

gray621, подсказка – количество делителей :
https://www.cyberforum.ru/cgi-bin/latex.cgi?prod_{}^{}({{p}_{i}}^{} + 1)
Где https://www.cyberforum.ru/cgi-bin/latex.cgi?{p}_{i} – степень простого i-го множителя в составе исходного числа
24 -> 2*2*2*3 -> https://www.cyberforum.ru/cgi-bin/latex.cgi?{2}^{3} * {3}^{1}
Итого множителей = (3+1) * (1+1) = 8



1

gray621

36 / 51 / 11

Регистрация: 14.01.2021

Сообщений: 406

17.01.2021, 20:52

 [ТС]

4

Цитата
Сообщение от unfindable_404
Посмотреть сообщение

divs = int(input())
n = 1
while True:
    count_of_dividers = 0
    for i in range(n, 0, -1):
        if n % i == 0:
            count_of_dividers += 1
    if count_of_dividers == divs:
        print(n)
        break
    n += 1

Спасибо, у меня не получалось придумать ещё n, а так всё такое же.

Добавлено через 5 минут

Python 
1
2
3
4
5
6
7
8
9
10
11

divs = int(input())
n = 1
while True:
    count_of_dividers = 0
    for i in range(n, 0, -1):
        if n % i == 0:
            count_of_dividers += 1
    if count_of_dividers == divs:
        print(n)
        break
    n += 1

Код не работает на 18 тесте, превышен лимит времени, можно как-то ускорить цикл?



0

Эксперт Python

7250 / 4039 / 1779

Регистрация: 27.03.2020

Сообщений: 6,865

17.01.2021, 21:06

5

gray621, ограничения на “n” есть ?



0

36 / 51 / 11

Регистрация: 14.01.2021

Сообщений: 406

17.01.2021, 21:23

 [ТС]

6

Цитата
Сообщение от Gdez
Посмотреть сообщение

ограничения на “n” есть ?

Нет, но есть ограничение на время 1 секунда, а тест идёт 1064 ms, то есть нужно ускорить цикл немножко.

Добавлено через 15 минут
Я думаю можно уменьшить время пополам если уменьшить в range number пополам, т.к. делителей больше половины числа нет. Как это реализовать если в range int?



0

3478 / 2086 / 559

Регистрация: 02.09.2015

Сообщений: 5,329

17.01.2021, 21:35

7

Нарыл решение

Но оно не удовлетворяет условию:

Цитата
Сообщение от gray621
Посмотреть сообщение

При решении нельзя использовать функции и методы, а также списки и словари.

В т. ч. мемоизация.



0

Gdez

Эксперт Python

7250 / 4039 / 1779

Регистрация: 27.03.2020

Сообщений: 6,865

17.01.2021, 22:08

8

Лучший ответ Сообщение было отмечено gray621 как решение

Решение

gray621, если не ошибся

Python 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

divs = int(input())
if divs % 2 :
    n = 1
    while True:
        if int(n**0.5) == n**0.5 :
            count_of_dividers = 1
            for i in range(1, int(n**0.5)):
                if n % i == 0:
                    count_of_dividers += 2
            if count_of_dividers == divs:
                print(n)
                break
        n += 1
else :
    n = divs
    while True:
        if int(n**0.5) != n**0.5 :
            count_of_dividers = 0
            for i in range(1, int(n**0.5) + 1) :
                if n % i == 0 :
                    count_of_dividers += 2
            if count_of_dividers == divs:
                print(n)
                break
        n += 2

Добавлено через 7 минут
Arsegg, на кодфорсе как то набрел на задачку по делителям. Вроде решил – тесты все прошла. Но позже сам нашел при каких N неверно считает мой код. Там через плюсики с реккурсией решили.
Если интересует, то возможно найду задачу на кодфорс. А тут я выкладывал тему :
Разложение на множители



1

Arsegg

17.01.2021, 22:34

Не по теме:

Цитата
Сообщение от Gdez
Посмотреть сообщение

Если интересует, то возможно найду задачу на кодфорс.

Полагаю, задача div1. 😀



0

gray621

36 / 51 / 11

Регистрация: 14.01.2021

Сообщений: 406

17.01.2021, 22:49

 [ТС]

10

Цитата
Сообщение от Gdez
Посмотреть сообщение

divs = int(input())
if divs % 2 :
    n = 1
    while True:
        if int(n**0.5) == n**0.5 :
            count_of_dividers = 1
            for i in range(1, int(n**0.5)):
                if n % i == 0:
                    count_of_dividers += 2
            if count_of_dividers == divs:
                print(n)
                break
        n += 1
else :
    n = divs
    while True:
        if int(n**0.5) != n**0.5 :
            count_of_dividers = 0
            for i in range(1, int(n**0.5) + 1) :
                if n % i == 0 :
                    count_of_dividers += 2
            if count_of_dividers == divs:
                print(n)
                break
        n += 2

А почему там n в корень возводится, а не пополам делится?

Добавлено через 5 минут
Зачем проверка

Python 
1

if int(number ** 0.5) == number ** 0.5

?



0

Эксперт Python

7250 / 4039 / 1779

Регистрация: 27.03.2020

Сообщений: 6,865

17.01.2021, 23:11

11

Arsegg,

Добавлено через 5 минут
gray621,

А почему там n в корень возводится, а не пополам делится?

Потому что это не слагаемые, а делители. Допустим для 40 не нужно искать делители больше 6, сразу считать парами – 1 и 40, 2 и 20, 4 и 10, 5 и 8; всего 8 делителей.
Первый while перебирает квадраты чисел – у них нечетное число делителей.
Поэтому и проверка (это ответ на второй вопрос) – если число не квадрат другого числа, то количество делителей четное

Добавлено через 5 минут
gray621, Кроме 1, остальные минимальные числа с заданным количеством делителей – четные. Поэтому, если N > 1, то счетчик можно с шагом 2 по четным числам



2

36 / 51 / 11

Регистрация: 14.01.2021

Сообщений: 406

17.01.2021, 23:25

 [ТС]

12

Цитата
Сообщение от Gdez
Посмотреть сообщение

если число не квадрат другого числа, то количество делителей четное

То есть у квадратов чисел корни натуральные числа?



0

Эксперт Python

7250 / 4039 / 1779

Регистрация: 27.03.2020

Сообщений: 6,865

17.01.2021, 23:41

13

gray621, нет
4 -> 1, 2, 4
9 -> 1, 3, 9
16 -> 1, 2, 4, 8 16
и тд
Допустим 36 -> (1 и 36) + (2 и 18) + (3 и 12) + (4 и 9) + (6 и 6)… Но 6 и 6 это одно число. Итого четыре пары делителей плюс один делитель (для 36 это 6). Это для всех чисел, которые квадраты какого то натурального делителя.

Добавлено через 2 минуты
А вообще, задача без функций и списков некорректна. Когда найдешь код, который пройдет все тесты, попробуй число, допустим, 59 или 77



0

gray621

36 / 51 / 11

Регистрация: 14.01.2021

Сообщений: 406

18.01.2021, 00:14

 [ТС]

14

Цитата
Сообщение от Gdez
Посмотреть сообщение

Когда найдешь код, который пройдет все тесты

Твой код прошёл

Добавлено через 15 секунд

Цитата
Сообщение от Gdez
Посмотреть сообщение

Когда найдешь код, который пройдет все тесты

Твой код прошёл

Добавлено через 10 секунд

Цитата
Сообщение от Gdez
Посмотреть сообщение

Когда найдешь код, который пройдет все тесты

Твой код прошёл

Добавлено через 22 минуты
Зачем проверка для чётного кол-во делителей

Python 
1

if int(number ** 0.5) != number ** 0.5:

И ещё почему в range + 1?

Python 
1

range(1, int(number ** 0.5) + 1):



0

Gdez

Эксперт Python

7250 / 4039 / 1779

Регистрация: 27.03.2020

Сообщений: 6,865

18.01.2021, 04:38

15

gray621,

Зачем проверка для чётного кол-во делителей

Потому что для четных диапазон :

Python 
1

range(1, int(number ** 0.5) + 1):

Для нечетных изначально можно не включать значение корня (для 36 число 6 уже входит -> count_of_dividers = 1)
Для четных нужно включать => допустим 42 -> его “целый” корень = 6 и для 6 парный делитель 7.
Если убрать проверку (что число не квадрат другого числа), то для N = 10 выведет ответ -> 36 -> посчитает пару (6 и 6)



1

IT_Exp

Эксперт

87844 / 49110 / 22898

Регистрация: 17.06.2006

Сообщений: 92,604

 18.01.2021, 04:38

Помогаю со студенческими работами здесь

Дано число P, нужно найти число от 1 до Р, с наибольшим количеством делителей
написал проггу, что не правильно уже 3 часа бьюсь…

int p;
int max=0,a = 0;
…

Дано натуральное число N. Найти число от 1 до N с максимальной суммою делителей
Дано натуральное число N. Найти число от 1 до N с максимальной суммой делителей.

Формат входных…

Дано натуральное число n. Найти число от 1 до n, имеющий как можно большее сумму делителей
Дано натуральное число n. Найти число от 1 до n, имеющий как можно большее сумму делителей.
Решать…

. Найти число всех натуральных делителей числа , которые не превосходят это число и взаимно простых с ним: а) 720, б) 3179, в) 6615
. Найти число всех натуральных делителей числа , которые не превосходят это число и взаимно…

Перестановка элементов массива по количеству делителей
Задание такое: Заполните массив случайными числами в интервале (100,999) и переставьте их по…

Расставьте данный массив натуральных чисел по количеству их делителей
Расставьте данный массив натуральных чисел по количеству их делителей.

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:

15

Источник

В данной статье мы поговорим о том, как найти все делители числа. Начнем с доказательства теоремы, с помощью которой можно задать вид всех делителей определенного числа. Далее возьмем примеры нахождения всех нужных делителей и покажем, как именно определить, сколько делителей имеет конкретное число. В последнем пункте подробно рассмотрим примеры задач на нахождение общих делителей нескольких чисел.

Как найти все делители числа

Чтобы понять материал, изложенный в данном пункте, нужно хорошо знать, что вообще из себя представляют кратные числа и делители. Здесь мы поговорим только о поиске делителей натуральных чисел, т.е. целых положительных. Этим можно ограничиться, поскольку свойство делимости гласит, что делители целого отрицательного числа аналогичны делителям целого положительного, которое будет противоположным по отношению к этому числу. Также сразу уточним, что у нуля есть бесконечно большое число делителей, и находить их смысла не имеет, поскольку в итоге все равно получится 0.

Если речь идет о простом числе, то его можно разделить только на единицу и на само себя. Значит, у любого простого числа a есть всего 4 делителя, два из которых больше 0 и два меньше: 1, -1, a, -a. Возьмем простое число 7: у него есть делители 7, -7, 1 и -1, и все. Еще один пример: 367 – тоже простое число, которое можно разделить лишь на 1, -1, 367 и -367.

Сложнее определить все делители составного числа. Сформулируем теорему, которая лежит в основе данного действия.

Теорема 1

Допустим, у нас есть выражение, означающее каноническое разложение числа на простые множители, вида a=p1s1·p2s2·…·pnsn. Тогда натуральными делителями числа a будут следующие числа: d=p1t2·p2t2·…·pntn, где t1=0, 1, …, s1, t2=0, 1, …, s2, …, tn=0, 1, …, sn.

Доказательство 1

Перейдем к доказательству этой теоремы. Зная основное определение делимости, мы можем утверждать, что a можно разделить на d, если есть такое число q, что делает верным равенство a=d·q, т.е. q=p1(s1−t1)·p2(s2-t2)·…·pn(sn-tn).

Любое число, делящее a, будет иметь именно такой вид, поскольку, согласно свойствам делимости, других простых множителей, кроме p1, p2, …, pn, оно иметь не может, а их показатели в данном случае не превысят s1, s2, …, sn.

Учитывая доказательство этой теоремы, мы можем сформировать схему нахождения всех положительных делителей данного числа.

Для этого нужно выполнить следующие действия:

  1. Выполнить каноническое разложение на простые множители и получить выражение вида a=p1s1·p2s2·…·pnsn.
  2. Найти все значения d=p1t2·p2t2·…·pntn, где числа t1, t2, …, tn будут принимать независимо друг от друга каждое из значений t1=0, 1, …, s1, t2=0, 1, …, s2, …, tn=0, 1, …, sn.

Самым трудным в таком расчете является именно перебор всех комбинаций указанных значений. Разберем подробно решения нескольких задач, чтобы наглядно показать применение данной схемы на практике.

Пример 1

Условие: найти все делители 8.

Решение

Разложим восьмерку на простые множители и получим 8=2·2·2.  Переведем разложение в каноническую форму и получим 8=23. Следовательно, a=8, p1=2, s1=3.

Поскольку все делители восьмерки будут значениями p1t1=2t1, то t1 может принять значения нуля, единицы, двойки, тройки. 3 будет последним значением, ведь s1=3. Таким образом, если t1=0, то 2t1=20=1, если 1, то 2t1=21=2, если 2, то 2t1=22=4, а если 3, то 2t1=23=8.

Для нахождения делителей удобно все полученные значения оформлять в виде таблицы:

t1 2t1
0 20=1
1 21=2
2 22=4
3 23=8

Значит, положительными делителями восьмерки будут числа 1, 2, 4 и 8, а отрицательными −1, −2, −4 и −8.

Ответ: делителями данного числа будут ±1, ±2, ±4, ±8.

Возьмем пример чуть сложнее: в нем при разложении числа получится не один, а два множителя.

Пример 2

Условие: найдите все делители числа 567, являющиеся натуральными числами.

Решение

Начнем с разложения данного числа на простые множители.

56718963217133337

Приведем разложение к каноническому виду и получим 567=34·7. Затем перейдем к вычислению всех натуральных множителей. Для этого будем присваивать t1 и t2 значения 0, 1, 2, 3, 4 и 0, 1, вычисляя при этом значения 3t1·7t2. Результаты будем вносить в таблицу:

t1 t2 3t1·7t2
0 0 30·70=1
0 1 30·71=7
1 0 31·70=3
1 1 31·71=21
2 0 32·70=9
2 1 32·71=63
3 0 33·70=27
3 1 33·71=189
4 0 34·70=81
4 1 34·71=567

Ответ: натуральными делителями 567 будут числа 27, 63, 81, 189, 1, 3, 7, 9, 21 и 567.

Продолжим усложнять наши примеры – возьмем четырехзначное число.

Пример 3

Условие: найти все делители 3 900, которые будут больше 0.

Решение

Проводим разложение данного числа на простые множители. В каноническом виде оно будет выглядеть как 3 900=22·3·52·13. Теперь приступаем к нахождению положительных делителей, подставляя в выражение 2t1·3t2·5t3·13t4 значения t1, равные 0, 1 и 2, t2=0,1, t3=0, 1, 2, t4=0, 1. Результаты представляем в табличном виде:

t1 t2 t3 t4 2t1·3t2·5t3·13t4
0 0 0 0 20·30·50·130=1
0 0 0 1 20·30·50·131=13
0 0 1 0 20·30·51·130=5
0 0 1 1 20·30·51·131=65
0 0 2 0 20·30·52·130=25
0 0 2 1 20·30·52·131=325
0 1 0 0 20·31·50·130=3
0 1 0 1 20·31·50·131=39
0 1 1 0 20·31·51·130=15
0 1 1 1 20·31·51·131=195
0 1 2 0 20·31·52·130=75
0 1 2 1 20·31·52·131=975
t1 t2 t3 t4 2t1·3t2·5t3·13t4
1 0 0 0 21·30·50·130=2
1 0 0 1 21·30·50·131=26
1 0 1 0 21·30·51·130=10
1 0 1 1 21·30·51·131=130
1 0 2 0 21·30·52·130=50
1 0 2 1 21·30·52·131=650
1 1 0 0 21·31·50·130=6
1 1 0 1 21·31·50·131=78
1 1 1 0 21·31·51·130=30
1 1 1 1 21·31·51·131=390
1 1 2 0 21·31·52·130=150
1 1 2 1 21·31·52·131=1950
t1 t2 t3 t4 2t1·3t2·5t3·13t4
2 0 0 0 22·30·50·130=4
2 0 0 1 22·30·50·131=52
2 0 1 0 22·30·51·130=20
2 0 1 1 22·30·51·131=260
2 0 2 0 22·30·52·130=100
2 1 0 1 22·30·52·131=1300
2 1 0 0 22·31·50·130=12
2 1 0 1 22·31·50·131=156
2 1 1 0 22·31·51·130=60
2 1 1 1 22·31·51·131=780
2 1 2 0 22·31·52·130=300
2 1 2 1 22·31·52·131=3900

Ответ: делителями числа 3 900 будут:195, 260, 300, 325, 390, 650, 780, 975, 75, 78, 100, 130, 150, 156, 13,15, 20, 25, 26, 30, 39, 50,52, 60, 65, 1, 2, 3, 4, 5, 6, 10, 12, 1 300, 1 950, 3 900

Как определить количество делителей конкретного числа

Чтобы узнать, сколько положительных делителей у конкретного числа a, каноническое разложение которого выглядит как a=p1s1·p2s2·…·pnsn, нужно найти значение выражения (s1+1) ·(s2+1) ·…·(sn+1). О количестве наборов переменных t1, t2, …, tn мы можем судить по величине записанного выражения.

Покажем на примере, как это вычисляется. Определим, сколько будет натуральных делителей у числа 3 900, которое мы использовали в предыдущей задаче. Каноническое разложение мы уже записывали: 3 900=22·3·52·13. Значит, s1=2, s2=1, s3=2, s4=1. Теперь подставим значения s1, s2, s3 и s4 в выражение (s1+1) ·(s2+1) ·(s3+1) ·(s4+1) и вычислим его значение. Имеем (2+1)·(1+1)·(2+1)·(1+1)=3·2·3·2=36. Значит, это число имеет всего 36 делителей, являющихся натуральными числами. Пересчитаем то количество, что у нас получилось в предыдущей задаче, и убедимся в правильности решения. Если учесть и отрицательные делители, которых столько же, сколько и положительных, то получится, что у данного числа всего будет 72 делителя.

Пример 4

Условие: определите, сколько делителей имеет 84.

Решение 

Раскладываем число на множители.

844221712237

Записываем каноническое разложение: 84=22·3·7. Определяем, сколько у нас получится положительных делителей: (2+1)·(1+1)·(1+1) =12. Для учета отрицательных нужно умножить это число на 2:2·12=24.

Ответ: всего у 84 будет 24 делителя – 12 положительных и 12 отрицательных.

Как вычислить общие делители нескольких чисел

Зная свойства наибольшего общего делителя, можно утверждать, что количество делителей некоторого набора целых чисел будет совпадать с количеством делителей НОД тех же чисел. Это будет справедливо не только для двух чисел, но и для большего их количества. Следовательно, чтобы вычислить все общие делители нескольких чисел, надо определить их наибольший общий множитель и найти все его делители.

Разберем пару таких задач.

Пример 5

Условие: сколько будет натуральных общих делителей у чисел 140 и 50? Вычислите их все.

Решение

Начнем с вычисления НОД (140, 50).

Для этого нам потребуется алгоритм Евклида:

140=50·2+40, 50=40·1+10, 40=10·4, значит, НОД (50, 140)=10.

Далее выясним, сколько положительных делителей есть у десяти. Разложим его на простые множители и получим 20·50=1, 20·51=5, 21·50=2 и  21·51=10. Значит, все натуральные общие делители исходного числа – это 1, 2, 5 и 10, а всего их четыре.

Ответ: данные числа имеют четыре натуральных делителя, равные 10, 5, 2 и 1.

Пример 6

Условие: выясните, сколько общих положительных делителей есть у чисел 585, 315, 90 и 45.

Решение

Вычислим их наибольший общий делитель, разложив число на простые множители. Поскольку 90=2·3·3·5, 45=3·3·5, 315=3·3·5·7 и 585=3·3·5·13, то таким делителем будет 5: НОД (90, 45, 315, 585) =3·3·5=32·5.

Чтобы узнать количество этих чисел, нужно выяснить, сколько положительных делителей имеет НОД.

Считаем:

НОД (90, 45, 315, 585) =32·5:(2+1)·(1+1) =6.

Ответ: у данных чисел шесть общих делителей.

Источник

34K

06 апреля 2008 года

Carbon

17 / / 21.03.2008

Плохая задачка.
Только перебор, возможно, немного оптимизированный, больше ничего я в инете не нашёл, даже на сайте про последовательности, вот тут универсальной формулы для этой последовательности (миннимальное число с заданным количеством делителей) нет.

Немного опоздал с ответом, но вот моё решение:
1) Количество простых делителей 12 (2^12=4096, 2^13=8192). Будем работать с разложением числа. Тогда выписываем первые 12 простых чисел.
2) D раскладываем на простые множители и сопоставляем их каждому простому числу в порядке убывания (84=2*2*3*7 => 2:6, 3:2, 5:1, 7:1).
3) Получаем число 2^6*3^2*5^1*7^1. Проходим по степеням с конца массива. Если число уменьшится при переносе степени на более раннюю позицию, то выполнится условие: a^u*b^v>a^((u+1)*(v+1)-1) (a<b).
Получаем: lnb>(u+1)lna. Если это условие выполняется, то при переносе число уменьшится. Для максимального уменьшения выбираем минимум чисел (u+1)lna. Для числа a ставим степень (u+1)*(v+1)-1, для числа b – 0.
4) Проходим по массиву и находим произведение чисел a^u. Если число превышает 10^15+1, то останавливаемся.

Общая сложность алгоритма O(sqrt(D)). Можно оптимизировать шаг 3), но и так скорость высокая, поэтому не стОит. И никакого перебора не нужно.

Код:

#include <stdio.h>
#include <math.h>

int main(int argc, char* argv[])
{
    const long long limit=100000I64*100000I64*100000I64+1I64;
    double min,v;
    long long res=1I64;
    int D,nums[12]={2,3,5,7,11,13,17,19,23,29,31,37},
    divisors[12],temp[12],count=0,index;
    bool stop;

    scanf(“%d”,&D);
    index=sqrt((double)D);
    for (int i=2;i<=index;)
        if (D%i==0)
        {
            D/=i;
            temp[count]=i-1;
            count++;
        }
        else
            i++;

    if (D>1)
    {
        temp[count]=D-1;
        count++;
    }

    for (int i=0;i<count;i++)
        divisors[count-1-i]=temp;

    for (int i=count-1;i>=1;i–)
    {
        min=30000.0;
        for (int j=i-1;j>=0;j–)
        {
            v=(double)(divisors[j]+1)*log((double)nums[j]);
            if (v<min)
            {
                min=v;
                index=j;
            }
        }
        if (min<log((double)nums))
        {
            divisors[index]=(divisors[index]+1)*(divisors+1)-1;
            divisors=0;
        }
    }

    stop=false;
    for (int i=0;i<count&&!stop;i++)
        for (int j=0;j<divisors&&!stop;j++)
        {
            res*=(long long)nums;
            stop=res>limit;
        }

    if (stop)
        printf(“0”);
    else
        printf(“%I64d”,res);

    getchar();
    getchar();

    return 0;
}

Источник

Добавить комментарий