Как найти натуральное число по количеству делителей - Autoru.top

gray621

36 / 51 / 11

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

Сообщений: 406

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

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

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

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

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

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

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

Python

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)

unfindable_404

690 / 473 / 204

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

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

17.01.2021, 20:32

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

Python

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

7256 / 4045 / 1780

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

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

17.01.2021, 20:42

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

gray621

36 / 51 / 11

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

Сообщений: 406

17.01.2021, 20:52

[ТС]

Сообщение от 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

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 тесте, превышен лимит времени, можно как-то ускорить цикл?

7256 / 4045 / 1780

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

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

17.01.2021, 21:06

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

36 / 51 / 11

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

Сообщений: 406

17.01.2021, 21:23

[ТС]

Сообщение от Gdez

ограничения на «n» есть ?

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

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

3483 / 2090 / 560

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

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

17.01.2021, 21:35

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

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

Сообщение от gray621

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

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

Gdez

7256 / 4045 / 1780

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

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

17.01.2021, 22:08

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

Решение

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

Python

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 неверно считает мой код. Там через плюсики с реккурсией решили.
Если интересует, то возможно найду задачу на кодфорс. А тут я выкладывал тему :
Разложение на множители

Arsegg

17.01.2021, 22:34

Не по теме:

Сообщение от Gdez

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

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

gray621

36 / 51 / 11

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

Сообщений: 406

17.01.2021, 22:49

[ТС]

Сообщение от 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

7256 / 4045 / 1780

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

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

17.01.2021, 23:11

Arsegg,

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

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

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

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

36 / 51 / 11

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

Сообщений: 406

17.01.2021, 23:25

[ТС]

Сообщение от Gdez

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

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

7256 / 4045 / 1780

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

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

17.01.2021, 23:41

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

gray621

36 / 51 / 11

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

Сообщений: 406

18.01.2021, 00: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):

Gdez

7256 / 4045 / 1780

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

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

18.01.2021, 04:38

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)

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.04.2011, 23:51
24/03/09 43 Питер	Всем привет. Друзья, попала мне вот такая вот, казалось бы, не сложная задачка: Нам известно, что у числа делителей. (Включая и само число ). Чему равно это , если сумма делителей равно ? P.S. Нашел в интернете похожую задачку. Условие такое же, только сумма равна . В таком случае подходит число 75, ведь: Возможно в моем условии очепятка и там должно стоять число 124? Но как доказать в случае 124=>75 я тоже не очень понял. Благодарю за помощь!

ИСН

Re: Делители

16.04.2011, 00:16

Заслуженный участник

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

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

svv

Re: Делители

16.04.2011, 00:36

Заслуженный участник

23/07/08
10074
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
5849
Новосибирск

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

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

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

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

VAL

Re: Делители

16.04.2011, 08:05

Заслуженный участник

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

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

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

‘а.
1) не подходит);
2)
И первое же $q$ дает ответ.

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

Источник

Число и сумма натуральных делителей натурального числа
Основная теорема арифметики. Всякое натуральное число п > 1 либо просто, либо может быть представлено, и притом единственным образом — с точностью до порядка следования сомножителей, в виде произведения простых чисел (можно считать, что любое натуральное число, большее 1, можно представить в виде произведения простых чисел, если считать , что это произведение может содержать всего лишь один множитель).
Среди простых сомножителей, присутствующих в разложении `n = p1*p2*…*pk`, могут быть и одинаковые. Например, `24=2*2*2*3`. Их можно объединить, воспользовавшись операцией возведения в степень. Кроме того, простые сомножители можно упорядочить по величине. В результате получается разложение
`n = p_1^(alpha_1)*p_2^(alpha_2)*…….*p_k^(alpha_k)`, где `alpha_1, alpha_2, ……, alpha_k in NN`
(1)
Такое представление числа называется каноническим разложением его на простые сомножители. Например, каноническое представление числа 2 520 имеет вид 2 520 = 2³ • З² • 5 • 7.
Из канонического разложения числа легко можно вывести следующую лемму: Если n имеет вид (1), то , то все делители этого числа имеют вид:
`d = p_1^(beta_1)*p_2^(beta_2)*……*p_k^(beta^k)`, где `0 <= beta_m <= alpha_m` ( `m = 1,2,…, k`)
(2)
В самом деле, очевидно, что всякое d вида (2) делит а. Обратно, пусть d делит а, тогда a=cd, где с — некоторое натуральное число и, следовательно, все простые делители числа d входят в каноническое разложение числа а с показателями, не превышающими соответствующих показателей числа а.
Рассмотрим две функции, заданные на множестве натуральных чисел:
а) τ(n) — число всех натуральных делителей n;
2) σ(n) сумма всех натуральных делителей числа n.
Пусть n имеет каноническое разложение (1). Выведем формулы для числа и суммы его его натуральных делителей.
Теорема 1. Число натуральных делителей числа n
`tau(n) = (alpha_1 + 1)*(alpha_2 + 1)*…..*(alpha_k + 1);`
(3)
Доказательство.
читать дальше
Пример. Число 2 520 = 2³ • З² • 5 • 7. имеет (3+1)(2+1)(1+1)(1+1) = 48 делителей.
Теорема 2. Пусть n имеет каноническое разложение (1). Тогда сумма натуральных делителей числа n равна
`sigma(n) = (1 + p_1 + p_1^2 + ….. + p_1^(alpha_1))*(1 + p_2 + p_2^2 + ….. + p_2^(alpha_2))* …………..* (1 + p_k + p_k^2 + …..+ p_k^(alpha_k));`
(4)
Доказательство.
читать дальше
Пример. Найти сумму всех делителей числа 90.
90=2 • З² • 5. Тогда σ(90)=[(2²-1)/(2-1)]• [З³-1)/(3-1)]• [(5²-1)/(5-1)]=234
Формула (4) может помочь найти все делители числа.Так, например, чтобы найти все делители числа 90, раскроем скобки в следующем произведении (не производя операцию сложения): (1+2)(1+3+З²)(1+5)=(1+1*3+1*З²+1*2+2*3+2*З²)(1+5) = 1+3+З²+2+2*3+2*З²+ 5+3*5+З²*5+2*5+2*3*5+2*З²*5 = 1+3+9+2+6+18+5+15+45+10+30+90 — слагаемыми являются делители числа 90.
Решим несколько задач на тему «Число и сумма натуральных делителей натурального числа»
Задание 1. Найдите натуральное число, зная, что оно имеет только два простых делителя, что число всех делителей равно 6, а сумма всех делителей — 28.
Решение
Задания из сборника TTZ — ЕГЭ 2010. Математика. Типовые тестовые задания
Задание 2. TTZ.С6.2 Найдите все натуральные числа, которые делятся на 42 и имеют ровно 42 различных натуральных делителя (включая единицу и само число).
Решение
Задание 3. TTZ.С6.9 Найдите все натуральные числа, последняя десятичная цифра которых 0 и которые имеют ровно 15 различных натуральных делителей(включая единицу и само число).
Решение
Задание 4. SPI.С6.9. У натурального числа n ровно 6 делителей. Сумма этих делителей равна 3500. Найти n.
Решение VEk:
Решение

Задания для самостоятельной работы
SR1. Найти все числа, имеющие ровно 2 простых делителя, всего 8 делителей, сумма которых равна 60.
SR2. Найти натуральные числа, которые делятся на 3 и на 4 и имеют ровно 21 натуральный делитель.
SR3. Найти наименьшее натуральное число, имеющее ровно 18 натуральных делителей.
SR4. Найти наименьшее число, кратное 5, имеющее 18 натуральных делителей.
SR5. Некоторое натуральное число имеет два простых делителя. Его квадрат имеет всего 15 делителей. Сколько делителей имеет куб этого числа?
SR6. Некоторое натуральное число имеет два простых делителя. Его квадрат имеет всего 81 делитель. Сколько делителей имеет куб этого числа?
SR7. Найти число вида m = 2^x3^y5^z, зная, что половина его имеет на 30 делителей меньше, треть —на 35 и пятая часть — на 42 делителя меньше, чем само число.

Топик поднят, поскольку по теме топика постоянно появляются вопросы.

Источник

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;
}
}