0 / 0 / 0
Регистрация: 08.10.2019
Сообщений: 13
1

Делители

08.10.2019, 17:10. Показов 3059. Ответов 3
Метки нет (Все метки)

Author24 — интернет-сервис помощи студентам
Задано число n. Требуется найти число от 1 до n, включительно, которое имеет
максимальное число положительных целых делителей.
Например, если n = 20, то искомое число — 12, у него 6 делителей: 1, 2, 3, 4, 6, 12.
-------------------------------------------------------------
Формат входных данных
На вход подается одно число n (1 ≤ n ≤ 105)
-------------------------------------------------------------
Формат выходных данных
Выведите на первой строке число от 1 до n, включительно, которое имеет мак-
симальное число делителей. На второй строке выведите число его делителей.
Если есть несколько чисел от 1 до n с максимальным числом делителей, выведите
любое из них.
------------------------------------------------------------
Примеры
standard input
20
standard output
12
6
0
Лучшие ответы (1)
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
08.10.2019, 17:10
Ответы с готовыми решениями:

Получить все простые делители числа
Дано натуральное число N. Получить все простые делители этого числа. Решите с помощью for

Найти все простые делители натурального числа N
Нужно нарисовать блок-схему :cry: program ZCHT7; uses crt; var i,n,j,a,flag:longint; ...

Вывести на экран все делители переданного процедуре числа
Напишите программу, в которой будет процедура, которая выводит на экран все делители переданного ей...

Для каждого числа в цикле найти его делители
дан цикл от 1 до N(вводим сами), и для каждого числа в цикле, найти его делители. Помогите пж

3
Почетный модератор
64299 / 47594 / 32743
Регистрация: 18.05.2008
Сообщений: 115,181
08.10.2019, 17:29 2
Наверное 1<n<=105?
1
0 / 0 / 0
Регистрация: 08.10.2019
Сообщений: 13
08.10.2019, 17:35  [ТС] 3
да,сейчас исправлю

Добавлено через 4 минуты
Можешь пожалуйста помочь,завтра олимпиада ,а я решить не могу,очень срочно нужно
0
Эксперт Pascal/Delphi
2386 / 1298 / 1492
Регистрация: 29.08.2014
Сообщений: 4,661
08.10.2019, 17:52 4
Лучший ответ Сообщение было отмечено Evgexa92 как решение

Решение

не мое
Pascal
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
26
27
28
29
30
31
32
//отсюда https://**********************/questions/352481/%D0%9F%D0%BE%D0%B8%D1%81%D0%BA-%D1%87%D0%B8%D1%81%D0%BB%D0%B0-%D0%B8%D0%BC%D0%B5%D1%8E%D1%89%D0%B5%D0%B3%D0%BE-%D0%BD%D0%B0%D0%B8%D0%B1%D0%BE%D0%BB%D1%8C%D1%88%D0%B5%D0%B5-%D1%87%D0%B8%D1%81%D0%BB%D0%BE-%D0%B4%D0%B5%D0%BB%D0%B8%D1%82%D0%B5%D0%BB%D0%B5%D0%B9
var  p:array of integer:=(2,3,5,7,11,13,17,19,23,29,31,37,41,43,47);
     answer, cntForAnswer,N:int64;
 
//index - индекс простого числа p[index], на который сейчас будем пробовать умножать
//lastA - значение предыдущего значения ai, что бы составить не возрастающую (a[i+1]<=a[i])
//value - текущее значние (p1^a1)*(p2^a2)*...*(pi^ai)
//cntForValue - количество делителей числа value
procedure findMax(index, lastA, value, cntForValue:int64);
begin
    if (cntForValue > cntForAnswer) or ((cntForValue = cntForAnswer) and (value < answer)) then begin
        answer := value;
        cntForAnswer := cntForValue;
    end;
    if(index = 15) then exit;
    for var a:=1 to lastA do begin
        var temp := value * p[index];
        // проверка на переполнение
        if(temp/p[index] <> value) then exit;
        // если получили число больше N
        if(temp > N) then break;
        value := temp;
        findMax(index+1, a, value, cntForValue*(a+1));
    end;
end;
 
begin
  readln(n);
  findMax(0, 64, 1, 1);
  writeln(answer);
  writeln(cntForAnswer);
end.
алгоритм
Существует решение и для чисел до 10^18.

Обозначения

Пусть искомое число X представимо в виде: (p1^a1)(p2^a2)...*(pk^ak), где pi - простое число, причем pi < pj при i < j, т.е. простые числа взяты по возрастанию.

Количество делителей cnt(X) = (a1+1)(a2+1)...*(ak+1) - это справедливо, даже если какие то степени ai = 0

Наблюдения:

Количество делителей зависят от показателей степени простого числа, которое в него входит, но не от самого простого числа.
Пусть последней ненулевой степенью будет ak, надо заметить, что нам не выгодно что бы на отрезке i=1...k-1 была ai=0, это значило бы, что мы можем сдвинуть массив степеней влево и при этом: число уменьшится, количество делителей останется таким же.
Так же нам выгодно, что бы массив ai создавал невозрастающую последовательность, иначе мы можем отсортировать данным массив по не возрастанию и мы получим меньшее число с таким же количеством делителей.
Количество простых чисел которое мы хотим рассматривается k<=15 для N<=10^18. Из соображений, что если перемножить первые 16 простых чисел получим число превышающее 10^18.
Из этих соображений строим алгоритм:

Необходимо перебрать все возможные последовательности ai не более из 15 элементов, удовлетворяющие следующим условиям:

последовательность ai - невозрастающая
(p1^a1)(p2^a2)...*(pk^ak) <= N
Среди таких последовательностей выбрать ту, где (a1+1)(a2+1)...*(ak+1) - максимально.
1
08.10.2019, 17:52
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
08.10.2019, 17:52
Помогаю со студенческими работами здесь

Вывести на дисплей простые делители натурального числа с использованием подпрограмм.
Составьте программу вывода на экран дисплея простых делителей натурального числа N с использованием...

Вывести на экран все простые делители чисел (отредактировать код)
Вывести на экран все простые делители чисел с диапазона от А до В в виде: число - список простых...

Вывести на экран все простые делители чисел из диапазона от А до В (с использованием функций)
Вывести на экран все простые делители чисел из диапазона от А до В в виде: число - список простых...

Даны целые числа q и p. Получить все делители числа q, взаимно кратные с p
Даны целые числа q и p. Получить все делители числа q , взаимно кратные с p


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

Или воспользуйтесь поиском по форуму:
4
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2024, CyberForum.ru