Наибольший натуральный делитель

@Tviks7771lp · Регистрация: 13.07.2022

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

Найдите наибольший большой натуральный делитель. На вход подаётся одно число. Делитель должен быть отличен от самого числа. Пример ввода: 16
Вывод: 8
тут выводит числа: 2 4 8 (а нужно только 8)

Java

public static void main(String[] args) {
        System.out.println("hello world");
        int number;
        Scanner scanner = new Scanner(System.in);
        number = scanner.nextInt();
        scanner.close();
 
        int count = 2;
 
        while (count < number ){
            if (number % count ==0){
                System.out.println(count);
            }
            count++;
        }
    }

@xoraxax · 13.07.2022, 17:55

ну, видимо, надо с введенного числа-1 начать

@Catstail · 13.07.2022, 18:55

xoraxax, необязательно. Можно и так:

Java

   int count = 2;
   while (count*count <= number )
   {
            if (number % count ==0)
            {
                System.out.println(number/count);
            }
            count++;
   }

@Whitecolor · 13.07.2022, 19:00

Catstail, В таком решении лишнее число выводиться

@Catstail · 13.07.2022, 19:37

Whitecolor, и не одно! Надо так:

Java

   int count = 2;
   while (count*count <= number )
   {
            if (number % count ==0)
            {
                System.out.println(number/count);
                break;
            }
            count++;
   }

@Whitecolor · 13.07.2022, 20:50

Catstail, Наверное эту задачу проще не через while решать, не совсем очевидное решение

@Catstail · 13.07.2022, 20:55

Whitecolor, совершенно очевидное... Что тут непонятно-то?

@Whitecolor · 13.07.2022, 21:10

Catstail, Что переменную count надо умножать на себя же

@Catstail · 14.07.2022, 07:07

Whitecolor, а, голубчик... Не "умножать на себя"... Предположим, что ты нашел делитель number:

$https://www.cyberforum.ru/cgi-bin/latex.cgi?number=count*k$

Здесь k - целое. Но тогда или

$https://www.cyberforum.ru/cgi-bin/latex.cgi?count <= \sqrt{number}$

или

$https://www.cyberforum.ru/cgi-bin/latex.cgi?k <= \sqrt{number}$

Почему? Предположим противное, т.е.

$https://www.cyberforum.ru/cgi-bin/latex.cgi?k > \sqrt{number}$

и

$https://www.cyberforum.ru/cgi-bin/latex.cgi?count > \sqrt{number}$

Перемножаем два последних неравенства и получаем:

$https://www.cyberforum.ru/cgi-bin/latex.cgi?k*count > \sqrt{number} * \sqrt{number} = number$

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

Поэтому для поиска всех делителей целого достаточно проверить последовательность 2,3,...k при k²<=n.

А девятиклассники этого не знают, и проверяют в лучшем случае диапазон 2,3,... n//2. Самые "выдающиеся" - 2,3,...n

Пусть мы ищем делители числа, не превышающего 100. При правильном подходе достаточно проверить 10 значений (2,3,...10). Девятиклассник будет проверять (2,3,...50). А самый ~~тупой~~ "продвинутый" проверит все числа до 100. т.е. в 10 раз больше.

С математикой нужно дружить!

Наибольший натуральный делитель

Решение

Решение

@xoraxax 3639 / 2971 / 918 Регистрация: 05.07.2013 Сообщений: 14,220
	13.07.2022, 17:55	2
	ну, видимо, надо с введенного числа-1 начать 1

@Whitecolor 802 / 565 / 74 Регистрация: 10.03.2012 Сообщений: 4,009
	13.07.2022, 19:00	4
	Catstail, В таком решении лишнее число выводиться 1

@Whitecolor 802 / 565 / 74 Регистрация: 10.03.2012 Сообщений: 4,009
	13.07.2022, 20:50	6
	Catstail, Наверное эту задачу проще не через while решать, не совсем очевидное решение 0

@Catstail Модератор 36606 / 20334 / 4221 Регистрация: 12.02.2012 Сообщений: 33,651 Записей в блоге: 13
	13.07.2022, 20:55	7
	Whitecolor, совершенно очевидное... Что тут непонятно-то? 0

@Whitecolor 802 / 565 / 74 Регистрация: 10.03.2012 Сообщений: 4,009
	13.07.2022, 21:10	8
	Catstail, Что переменную count надо умножать на себя же 0

@Catstail Модератор 36606 / 20334 / 4221 Регистрация: 12.02.2012 Сообщений: 33,651 Записей в блоге: 13
	14.07.2022, 07:07	9
	Сообщение было отмечено xoraxax как решение Решение Whitecolor, а, голубчик... Не "умножать на себя"... Предположим, что ты нашел делитель number: $https://www.cyberforum.ru/cgi-bin/latex.cgi?number=countk$ Здесь k - целое. Но тогда или $https://www.cyberforum.ru/cgi-bin/latex.cgi?count <= \sqrt{number}$ или $https://www.cyberforum.ru/cgi-bin/latex.cgi?k <= \sqrt{number}$ Почему? Предположим противное, т.е. $https://www.cyberforum.ru/cgi-bin/latex.cgi?k > \sqrt{number}$ и $https://www.cyberforum.ru/cgi-bin/latex.cgi?count > \sqrt{number}$ Перемножаем два последних неравенства и получаем: $https://www.cyberforum.ru/cgi-bin/latex.cgi?kcount > \sqrt{number} * \sqrt{number} = number$ Получаем противоречие. Мы доказали что если число представляется произведением двух целых, то хотя бы одно из них не должно превышать корень из этого числа (или, что то же самое) - квадрат одного из сомножителей не может превышать исходное число. Поэтому для поиска всех делителей целого достаточно проверить последовательность 2,3,...k при k²<=n. А девятиклассники этого не знают, и проверяют в лучшем случае диапазон 2,3,... n//2. Самые "выдающиеся" - 2,3,...n Пусть мы ищем делители числа, не превышающего 100. При правильном подходе достаточно проверить 10 значений (2,3,...10). Девятиклассник будет проверять (2,3,...50). А самый ~~тупой~~ "продвинутый" проверит все числа до 100. т.е. в 10 раз больше. С математикой нужно дружить! 3