Как найти максимальный делитель натурального числа - Сайт, где вы сможете решить свои вопросы

Разобрался в данной задаче и хочу показать свою получившуюся программу, и может понятно объяснить принцип ее работы (она достаточно эффективна – без массивов и списков, содержит только один вложенный цикл и пару условий). Язык – Java.

public class Main {

public static void main(String[] args) {

                     //необходимые переменные
    int number = 10; //число, которое нужно проверить
    int i = number;  //переменная для первого цикла
    int j = 0;       //счетчик кол-ва делителей у делителя (i) числа number
    int k;           //переменная для второго цикла

                                     //начало цикла (основной)
    while (i > 0) {                  //первый цикл до тех пор, пока делитель (i) числа number будет > 0
        if (number % i == 0) {       //проверяем остаток от деления числа number на i (сам делитель)
            k = i;
                                     //начало цикла (второй)
            while (k > 0) {          //второй цикл, проверяем делители у i (i - делитель number)
                if (i % k == 0) {    //если i делится на k (k - делитель) без остатка,
                    j++;             //увеличиваем счетчик
                }
                k--;                 //подбираем следующее k
            }
            if (j == 2) {            //анализируем счетчик. Если кол-во делителей (k) у i = 2,
                                     //то число подходит => выводим его на экран
                System.out.print("Наибольший простой делитель числа " + number + ": " + i);
                break;               //т.к. мы искали число, постепенно уменьшая наибольший возможный
                                     //делитель, то первое попавшееся нам подходит, значит можно
                                     //сразу закончить работу программы
            }
            j = 0;                   //аннулирование счетчика. Если текущее значение нам не подошло,
                                     //значит нужен чистый счетчик для след. числа
        }
        i--;                         //подбираем следующее i, если текущее нам не подходит
    }                                //конец первого цикла
    }
}

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

Важной частью программы является счетчик (j). Он будет считать кол-во делителей у делителя числа. Если это число равно двум, значит оно является простым (а простое число делится только на 1 и на само себя) и оно нам подходит. Можно заканчивать программу и выводить число на экран.

Источник

Полный текст программы

Простые делители числа 13195 – это 5, 7, 13 и 29.
Каков самый большой делитель числа 600851475143, являющийся простым числом?

Начну разбор с функции is_simple(n), определяющей является ли число простым.

Задача Эйлера 3 - Наибольший простой делитель

Тут нужны несколько замечаний:

Простое число по определению делится лишь на 1 и само на себя.
При этом не обязательно для проверки делить на все числа от 1 до самого числа, т.к. если число вообще делится, то его можно представить в виде произведения двух чисел a*b, при это чем больше a, тем меньше b. После того как они сравняются (a==b), множители будут повторяться, т.е. a начнет принимать значения, которые ранее принимало b и наоборот.
Таким образом в функции число n для проверки делится на все числа до квадратного корня из проверяемого числа включительно.
Если встречается делитель, который нацело делит проверяемое число n, то работа функции прерывается оператором break и возвращается результат False
Если по окончании перебора всего ряда ни одно из чисел не делит проверяемое число n нацело, значит оно является простым и функция возвращает True

Функция div_number(n) определяет максимальный делитель числа

Предполагается, что число n можно разложить на два множителя a*b
Число n последовательно делится на с каждой итерацией увеличивающееся (i+=1) число i
Как только число n делится без остатка искомый максимальный делитель найден

Работа самой программы

Вычисляется максимальный делитель числа N с помощью функции div_number(N)
Полученный результат проверяется с помощью функции is_simple(N)
Если число простое, то работы программы заканчивается и выводится результат
Если нет, то число очередной раз делится и вычисляется максимальный делитель уже от него

Собственно ответ

Источник

Рассмотрим два основных метода нахождения НОД двумя основными способами: с использованием алгоритма Евклида и путем разложения на простые множители. Применим оба метода для двух, трех и большего количества чисел.

Алгоритм Евклида для нахождения НОД

Алгоритм Евклида позволяет с легкостью вычислить наибольший общий делитель для двух положительных чисел. Формулировки и доказательство алгоритма Евклида мы привели в разделе «Наибольший общий делитель: определитель, примеры».

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

a=b·q1+r1, 0<r1<bb=r1·q2+r2, 0<r2<r1r1=r2·q3+r3, 0<r3<r2r2=r3·q4+r4, 0<r4<r3⋮rk-2=rk-1·qk+rk, 0<rk<rk-1rk-1=rk·qk+1

Мы можем закончить деление тогда, когда rk+1=0, при этом rk=НОД(a, b).

Пример 1

Найдите наибольший общий делитель чисел 64 и 48.

Решение

Введем обозначения: a=64, b=48.

На основе алгоритма Евклида проведем деление 64 на 48.

Получим 1 и остаток 16. Получается, что q1=1, r1=16.

Вторым шагом разделим 48 на 16, получим 3. То есть q2=3, а r2=0. Таким образом число 16 – это наибольший общий делитель для чисел из условия.

Ответ: НОД(64, 48)=16.

Пример 2

Чему равен НОД чисел 111 и 432?

Решение

Делим 432 на 111. Согласно алгоритму Евклида получаем цепочку равенств 432=111·3+99, 111=99·1+12, 99=12·8+3, 12=3·4.

Таким образом, наибольший общий делитель чисел 111 и 432 – это 3.

Ответ: НОД(111, 432)=3.

Пример 3

Найдите наибольший общий делитель чисел 661 и 113.

Решение

Проведем последовательно деление чисел и получим НОД(661, 113)=1. Это значит, что 661 и 113 – это взаимно простые числа. Мы могли выяснить это до начала вычислений, если бы обратились к таблице простых чисел.

Ответ: НОД(661, 113)=1.

Нахождение НОД с помощью разложения чисел на простые множители

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

Пример 4

Если мы разложим числа 220 и 600 на простые множители, то получим два произведения: 220=2·2·5·11 и 600=2·2·2·3·5·5. Общими в этих двух произведениях будут множители 2,2 и 5. Это значит, что НОД(220, 600)=2·2·5=20.

Пример 5

Найдите наибольший общий делитель чисел 72 и 96.

Решение

Найдем все простые множители чисел 72 и 96:

72361893122233

96482412631222223

Общими для двух чисел простые множители: 2, 2, 2 и 3. Это значит, что НОД(72, 96)=2·2·2·3=24.

Ответ: НОД(72, 96)=24.

Правило нахождения наибольшего общего делителя двух чисел основано на свойствах наибольшего общего делителя, согласно которому НОД(m·a1, m·b1)=m·НОД(a1, b1), где m– любое целое положительное число.

Нахождение НОД трех и большего количества чисел

Независимо от количества чисел, для которых нам нужно найти НОД, мы будем действовать по одному и тому же алгоритму, который заключается в последовательном нахождении НОД двух чисел. Основан этот алгоритм на применении следующей теоремы: НОД нескольких чисел a1, a2, …, ak равен числу dk, которое находится при последовательном вычислении НОД(a1, a2)=d2, НОД(d2, a3)=d3, НОД(d3, a4)=d4, …, НОД(dk-1, ak)=dk.

Пример 6

Найдите наибольший общий делитель четырех чисел 78, 294, 570 и 36.

Решение

Введем обозначения: a1=78, a2=294, a3=570, a4=36.

Начнем с того, что найдем НОД чисел 78 и 294: d2=НОД(78, 294)=6.

Теперь приступим к нахождению d3=НОД(d2, a3)=НОД(6, 570). Согласно алгоритму Евклида 570=6·95. Это значит, что d3=НОД(6, 570)=6.

Найдем d4=НОД(d3, a4)=НОД(6, 36). 36 делится на 6 без остатка. Это позволяет нам получить d4=НОД(6, 36)=6.

d4=6, то есть, НОД(78, 294, 570, 36)=6.

Ответ: НОД(78, 294, 570, 36)=6.

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

Пример 7

Вычислите НОД чисел 78, 294, 570 и 36.

Решение

Произведем разложение данных чисел на простые множители: 78=2·3·13, 294=2·3·7·7, 570=2·3·5·19, 36=2·2·3·3.

Для всех четырех чисел общими простыми множителями будут числа 2 и 3.

Получается, что НОД(78, 294, 570, 36)=2·3=6.

Ответ: НОД(78, 294, 570, 36)=6.

Нахождение НОД отрицательных чисел

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

Пример 8

Найдите НОД отрицательных целых чисел −231 и −140.

Решение

Для выполнения вычислений возьмем модули чисел, данных в условии. Это будут числа 231 и 140. Запишем это кратко: НОД(−231, −140)=НОД(231, 140). Теперь применим алгоритм Евклида для нахождения простых множителей двух чисел: 231=140·1+91; 140=91·1+49; 91=49·1+42; 49=42·1+7 и 42=7·6. Получаем, что НОД(231, 140)=7.

А так как НОД(−231, −140)=НОД(231, 140), то НОД чисел −231 и −140 равен 7.

Ответ: НОД(−231, −140)=7.

Пример 9

Определите НОД трех чисел −585, 81 и −189.

Решение

Заменим отрицательные числа в приведенном перечне на их абсолютные величины, получим НОД(−585, 81, −189)=НОД(585, 81, 189). Затем разложим все данные числа на простые множители: 585=3·3·5·13, 81=3·3·3·3 и 189=3·3·3·7. Общими для трех чисел являются простые множители 3 и 3. Получается , что НОД(585, 81, 189)=НОД(−585, 81, −189)=9.

Ответ: НОД(−585, 81, −189)=9.

Преподаватель математики и информатики. Кафедра бизнес-информатики Российского университета транспорта

Источник

0 / 0 / 0

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

Сообщений: 127

Максимальный делитель

12.10.2021, 16:46. Показов 3914. Ответов 3

Найдите максимальный делитель натурального числа n (n <= 100), отличный от самого числа.
Входные данные
В единственной строке натуральное число n > 1
Для примера:
Ввод
15
Result
5
Решить с помощью цикла while

Programming

Эксперт

94731 / 64177 / 26122

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

Сообщений: 116,782

12.10.2021, 16:46

Ответы с готовыми решениями:

Минимальный простой делитель
Минимальный простой делитель
Дано целое число, не меньшее 2. Выведите его наименьший простой…

Минимальный делитель
Дано целое число, не меньшее 2. Выведите его наименьший натуральный делитель, отличный от 1….

Минимальный простой делитель
Минимальный простой делитель

Дано целое число, не меньшее 2. Выведите его наименьший простой…

enx

1182 / 758 / 277

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

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

12.10.2021, 17:09

Shinskiy,

Python

n = int(input())
m = n // 2 - n % 2
while m > 0:
    if not n % m:
        print(m)
        break
    m -= 1

Catstail

Модератор

35330 / 19431 / 4065

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

Сообщений: 32,459

Записей в блоге: 13

12.10.2021, 18:14

Python

n=int(input("n="))
k=2
while k*k<=n:
    if n%k==0:
       print(n//k)
       break
    k+=1
else:
    print("Число-то простое...")

0 / 0 / 0

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

Сообщений: 1

17.03.2022, 12:42

Здравствуйте. А не могли бы пожалуйста объяснить, m что означает формула..

Источник

Для этого термина существует аббревиатура «НОД», которая имеет и другие значения, см. Нод.

Наибольшим общим делителем (НОД) для двух целых чисел и называется наибольший из их общих делителей^[1]. Пример: для чисел 54 и 24 наибольший общий делитель равен 6.

Наибольший общий делитель существует и однозначно определён, если хотя бы одно из чисел или не равно нулю.

Возможные обозначения наибольшего общего делителя чисел и :

Понятие наибольшего общего делителя естественным образом обобщается на наборы из более чем двух целых чисел.

Связанные определения[править | править код]

Наименьшее общее кратное[править | править код]

Наименьшее общее кратное (НОК) двух целых чисел и — это наименьшее натуральное число, которое делится на и (без остатка). Обозначается НОК(m,n) или [m,n] , а в английской литературе .

НОК для ненулевых чисел и всегда существует и связан с НОД следующим соотношением:

Это частный случай более общей теоремы: если $a_{1},a_{2},dots ,a_{n}$ — ненулевые числа, — какое-либо их общее кратное, то имеет место формула:

$D=[a_{1},a_{2},dots ,a_{n}]cdot left({frac {D}{a_{1}}},{frac {D}{a_{2}}},dots ,{frac {D}{a_{n}}}right)$

Взаимно простые числа[править | править код]

Числа и называются взаимно простыми, если у них нет общих делителей, кроме pm 1 . Для таких чисел НОД. Обратно, если НОД то числа взаимно просты.

Аналогично, целые числа $a_{1},a_{2},dots a_{k}$ , где kgeq 2 , называются взаимно простыми, если их наибольший общий делитель равен единице.

Следует различать понятия взаимной простоты, когда НОД набора чисел равен 1, и попарной взаимной простоты, когда НОД равен 1 для каждой пары чисел из набора. Из попарной простоты вытекает взаимная простота, но не наоборот. Например, НОД(6,10,15) = 1, но любые пары из этого набора не взаимно просты.

Способы вычисления[править | править код]

Эффективными способами вычисления НОД двух чисел являются алгоритм Евклида и бинарный алгоритм.

Кроме того, значение НОД(m,n) можно легко вычислить, если известно каноническое разложение чисел и на простые множители:

$n=p_{1}^{{d_{1}}}cdot dots cdot p_{k}^{{d_{k}}},$

$m=p_{1}^{{e_{1}}}cdot dots cdot p_{k}^{{e_{k}}},$

где $p_{1},dots ,p_{k}$ — различные простые числа, а $d_{1},dots ,d_{k}$ и $e_{1},dots ,e_{k}$ — неотрицательные целые числа (они могут быть нулями, если соответствующее простое отсутствует в разложении). Тогда НОД(n,m) и НОК[n,m] выражаются формулами:

$(n,m)=p_{1}^{{min(d_{1},e_{1})}}cdot dots cdot p_{k}^{{min(d_{k},e_{k})}},$

$[n,m]=p_{1}^{{max(d_{1},e_{1})}}cdot dots cdot p_{k}^{{max(d_{k},e_{k})}}.$

Если чисел более двух: $a_{1},a_{2},dots a_{n}$ , их НОД находится по следующему алгоритму:

$d_{2}=(a_{1},a_{2})$

$d_{3}=(d_{2},a_{3})$

………

$d_{n}=(d_{{n-1}},a_{n})$

— это и есть искомый НОД.

Свойства[править | править код]

Основное свойство: наибольший общий делитель и делится на любой общий делитель этих чисел. Пример: для чисел 12 и 18 наибольший общий делитель равен 6; он делится на все общие делители этих чисел: 1, 2, 3, 6.
Если делится на , то НОД(m, n) = n. В частности, НОД(n, n) = n.
. В общем случае, если , где – целые числа, то .
— общий множитель можно выносить за знак НОД.
Если , то после деления на числа становятся взаимно простыми, то есть, $left({{frac {m}{D}},{frac {n}{D}}}right)=1$ . Это означает, в частности, что для приведения дроби к несократимому виду надо разделить её числитель и знаменатель на их НОД.
Мультипликативность: если $a_{1},a_{2}$ взаимно просты, то:

$(a_{1}cdot a_{2},b)=(a_{1},b)cdot (a_{2},b)$

left{acdot m+bcdot nmid a,bin mathbb{Z } right}

и поэтому

представим в виде линейной комбинации чисел

Это соотношение называется соотношением Безу, а коэффициенты

— коэффициентами Безу. Коэффициенты Безу эффективно вычисляются расширенным алгоритмом Евклида. Это утверждение обобщается на наборы натуральных чисел — его смысл в том, что подгруппа группы

, порождённая набором ${a_{1},a_{2},dots ,a_{n}}$

, — циклическая и порождается одним элементом: НОД(a₁, a₂, … , a_n).

Вариации и обобщения[править | править код]

Понятие делимости целых чисел естественно обобщается на произвольные коммутативные кольца, такие, как кольцо многочленов или гауссовы целые числа. Однако, определить НОД(a, b) как наибольший из общих делителей , нельзя, так как в таких кольцах, вообще говоря, не определено отношение порядка. Поэтому в качестве определения НОД берётся его основное свойство:

Наибольшим общим делителем НОД(a, b) называется тот общий делитель, который делится на все остальные общие делители

Для натуральных чисел новое определение эквивалентно старому. Для целых чисел НОД в новом смысле уже не однозначен: противоположное ему число тоже будет НОД. Для гауссовых чисел число различных НОД возрастает до 4.

НОД двух элементов коммутативного кольца, вообще говоря, не обязан существовать. Например, для нижеследующих элементов и кольца не существует наибольшего общего делителя:

a=4=2cdot 2=left(1+{sqrt {-3}}right)left(1-{sqrt {-3}}right),qquad b=left(1+{sqrt {-3}}right)cdot 2.

В евклидовых кольцах наибольший общий делитель всегда существует и определён с точностью до делителей единицы, то есть количество НОД равно числу делителей единицы в кольце.

См. также[править | править код]

Бинарный алгоритм вычисления НОД
Делимость
Алгоритм Евклида
Наименьшее общее кратное

Литература[править | править код]

Виноградов И. М. Основы теории чисел. М.-Л.: Гос. изд. технико-теоретической литературы, 1952, 180 с.

Примечания[править | править код]

↑ Математическая энциклопедия (в 5 томах). — М.: Советская Энциклопедия, 1982. — Т. 3. страница 857

Источник

Простые делители числа 13195 – это 5, 7, 13 и 29.Каков самый большой делитель числа 600851475143, являющийся простым числом?

Алгоритм Евклида для нахождения НОД

Нахождение НОД с помощью разложения чисел на простые множители

Нахождение НОД трех и большего количества чисел

Нахождение НОД отрицательных чисел

Максимальный делитель

Связанные определения[править | править код]

Наименьшее общее кратное[править | править код]

Взаимно простые числа[править | править код]

Способы вычисления[править | править код]

Свойства[править | править код]

Вариации и обобщения[править | править код]

См. также[править | править код]

Литература[править | править код]

Примечания[править | править код]

Вам также может понравиться

Как найти коллинеарные векторы по данным координатам

Как по графику найти амплитуду колебания период

Как найти оптимизацию miui

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

Простые делители числа 13195 – это 5, 7, 13 и 29.
Каков самый большой делитель числа 600851475143, являющийся простым числом?