Как найти наименьший делитель для числа

Не слишком ли это простой вопрос? Очевидно, что надо лишь делить циклически на числа, начиная с 2, и проверять — делят ли они исходное число.

for i in range(2, x+1):
    if not x % i:
        print(i)
        break

Если число большое, то лучше остановить цикл на корне от x:

import math
for i in range(2, int(math.sqrt(x))+1):
    if not x % i:
        print(i)
        break
else:
    print(x)

Содержание:

Делимость чисел

Делители натурального числа

18 конфет можно разделить поровну между 3 детьми, дав каждому ребенку по 6. Это же количество конфет, не разрезая их, нельзя разделить поровну между 4 детьми. Если каждому ребенку дать по 4 конфеты, то останется 2. Запишем:

Число 18 делится на число 3 без остатка (еще говорят: 18 делится на 3). Число 3 называют делителем числа 18. Число 18 не делится без остатка на 4 (еще говорят: 18 не делится на 4). Число 4 не является делителем числа 18.

Любое натуральное число, на которое делится данное натуральное число, называют делителем этого числа.

Запишем все натуральные числа, на которые делится число 18 Такими числами являются 1,2,3,6,9, 18. Итак, число 18 имеет 6 делителей: 1,2, 3,6,9 и 18.

Число 1 имеет только один делитель — 1. Любое другое число, например, 23, обязательно имеет по крайней мере два делителя — число 1 и само число (23), причем I — наименьший делитель, само число (23) — наибольший.

Пример:

Найти все делители числа 36.

Решение:

Чтобы найти все делители числа 36, будем делить его на натуральные числа, начиная с 1: 36 : 1 = 36; 36 : 2 = 18; 36 : 3 = 12; 36 : 4 = 9; 36 : 5 = 7 (ост. 1); 36 : 6 = 6; 36 : 7 = 5 (ост. 1); 36 : 8 = 4 (ост. 4) и т. д.

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

Итак, делителями числа 36 являются: 1, 2, 3,4, 6, 9, 12, 18, 36.

Признаки делимости на 2, 5 и 10

Как известно из изученного в пятом классе, чтобы умножить натуральное число на 10, нужно к записи этого числа дописать справа один нуль, например, 137 • 10 = 1370. Поскольку 10 является делителем числа 1370, то число 1370 делится на 10. В общем, на 10 делятся все числа, запись которых оканчивается цифрой 0.

Число, запись которого не оканчивается цифрой 0, например, 457, на 10 не делится.

Натуральное число, запись которого оканчивается цифрой 0, делится на 10.

Натуральное число, запись которого не оканчивается цифрой 0, не делится на 10.

Это правило называют признаком делимости на 10.

Найдем признак делимости на 5. Для этого разделим на 5 некоторые числа, например, 19, 82, 140, 245, 344, 515, 630, 1027.

Запишем в первый столбик те числа, которые делятся на 5, а во второй — те, которые не делятся на 5.

Какую вы заметили особенность чисел, которые делятся на 5; не делятся на 5?

Натуральное число, запись которого оканчивается цифрой 0 или 5, делится на 5.

Натуральное число, запись которого оканчивается цифрой, отличной от 0 или 5, не делится на 5.

Числа, которые делятся на 2, называют четными, а числа, которые на 2 не делятся, — нечетными. Например, 24 — число четное, поскольку оно делится на 2, а число 25 — нечетное, поскольку оно не делится на 2.

Однозначные числа 0, 2,4, 6, 8 являются четными, а числа 1, 3, 5, 7, 9 — нечетными.

Запись каждого числа, которое делится на 2, оканчивается однозначным четным числом. Если запись числа оканчивается однозначным нечетным числом, то оно не делится на 2.

Натуральное число, запись которого оканчивается однозначным четным числом, делится на 2.

Натуральное число, запись которого оканчивается однозначным нечетным числом, не делится на 2.

Для тех, кто хочет знать больше

Зная последнюю цифру в записи натурального числа, можно установить, делится ли оно на 2, 5 или 10.

Зная две последние цифры в записи натурального числа, можно ответить на вопрос, делится ли число на 4, на 25. А именно:

Натуральное число делится на 4, если число, образованное двумя его последними цифрами, делится на 4.

Натуральное число не делится на 4, если число, образованное двумя его последними цифрами, не делится на 4

Натуральное число делится на 25. если число, образованное двумя его последними цифрами, делится на 25.

Натуральное число не делится на 25, если число, образованное двумя его последними цифрами, не делится на 25.

Например:

• 14 536 делится на 4, поскольку двумя его последними цифрами записано число 36, которое делится на 4;
• 57 375 делится на 25, поскольку 75 делится на 25;
• 28 426 не делится на 4, поскольку 26 не делится на 4;
• 438 635 не делится на 25, поскольку 35 не делится на 25.

Признаки делимости на 9 и на 3

Найдем признак делимости на 9. Для этого разделим на 9 некоторые числа, например, 288, 361,441, 814. 917, 8919.

Запишем в первый столбик те числа, которые делятся на 9, а во второй — те, которые не делятся на 9.

Какую вы заметили особенность чисел которые делятся на 9; не делятся на 9?

Воспользуйтесь такой подсказкой: найдите сумму цифр каждого из этих чисел.

Какое свойство имеет сумма цифр тех чисел, которые делятся на 9?

Какое свойство имеет сумма цифр тех чисел, которые не делятся на 9?

Натуральное число делится на 9, если сумма его цифр делится на 9.

Натуральное число не делится на 9, если сумма его цифр не делится на 9.

Признак делимости на 3 аналогичен признаку делимости на 9.

Натуральное число делится на 3, если сумма его цифр делится на 3.

Натуральное число не делится на 3, если сумма его цифр не делится на 3.

Для тех. кто хочет знать больше

Признак делимости на 9, например, для числа 468, следует из таких преобразований:

Число — 9 делится на 9. Сумма 4+6+8 является суммой цифр числа 468. Если она делится на 9, то и число 468 делится на 9. Так как сумма 4 + 6 + 8 = 18 делится на 9, то и число 468 делится на 9.

Простые и составные числа

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

Мы видим, что числа имеют разное количество делителей. Число 1 имеет только один делитель — само это число. Числа 2, 3, 17 имеют по два делителя: 1 и само себя. Числа 4, 12,21 и 30 имеют больше, чем два делителя.

Натуральное число называют простым, если оно имеет только два разных делителя: единицу и само это число. Число, имеющее более двух делителей, называют составным.

Итак, числа 2, 3, 17 — простые, а числа 4, 12, 21, 30 — составные. Число 1 не является ни простым, ни составным числом.

Если число имеет делитель, отличный от I и самого себя, то это число имеет более двух делителей и поэтому является составным. Число 12 475 — составное, так как имеет среди делителей, например, число 5.

Наименьшим простым числом является число 2. Наибольшего простого числа не существует. Все простые числа, кроме числа 2, являются нечетными.

Таблица простых чисел, которые не превышают 1000, находится на форзаце учебника.

Интересные рассказы

Решето Эратосфена

История математики знает имена ученых, которые приложили немало усилий для составления таблиц простых чисел. Первые такие попытки были сделаны еще в Древней Греции.

Для нахождения простых чисел древнегреческий ученый Эратосфен (ок. 276-ок. 194 г. до н.э.) предложил следующий способ Он выписывал все числа от 1 до некоторого числа Вычеркивал число 1, которое не является простым. Подчеркивал число 2 и вычеркивал все числа, которые делятся на 2, то есть числа 4, 6, 8, …. Следующее незачеркнутое число 3 является простым Эратосфен подчеркивал это число и вычеркивал все числа, которые делятся на 3 Подчеркивал следующее невычеркнутое число 5, которое является простым, и т. д. С помощью такого способа среди чисел, не превышающих можно «высеять» все простые числа.

Если «высеять» все простые числа, не превышающие 30, то получим:

2, 3, 5, 7, II, 13, 17, 19, 23, 29 — первые 10 простых чисел.

Эратосфенов метод «высевания» простых чисел называют еще «решетом Эратосфена». Это связано с тем, что древние греки писали на папирусе или табличках, покрытых воском, и числа не вычеркивали, а выкалывали иголкой, после чего папирус или табличка напоминали решето.

В 1603 году итальянский математик Пьетро Катальди опубликовал в Болонье первую известную нам таблицу простых чисел меньше 750. Позже математики продвигались все дальше в глубь натурального ряда чисел, открывая все новые и новые простые числа.

Уже в 1770 голу немецкий математик Иоанн Генрих Ламберт (1728- 1777) опубликовал таблицу наименьших делителей всех чисел меньше 102 000, которые не делятся на 2, 3 и 5. Это была огромная работа. Не зря, призывая ученых продолжить составление таблицы, Ламберт гарантировал бессмертие тому, кто получит таблицу делителей до 1 000 000.

В середине XIX века в прессе появились сообщения, которые казались совершенно невероятными: Венская академия наук получила рукопись пражского математика Якуба Филиппа Кулика, содержащую таблицу деятелей чисел, не делящихся 2, 3 и 5, которую ученый расширил до 100 миллионов.

Редактор таблиц простых чисел Лемер посетил Вену и убедился, что в библиотеке академии хранится семь больших томов рукописных таблиц «Большой канон делителей всех чисел, которые не делятся на 2, 3 и 5, и простых чисел между ними до 100 330 201 Якуба Филиппа Кулика, публичного ординарного профессора высшей математики Пражского университета».

Якуб Филипп Кулик (1793 1863) родился во Львове. Окончив местную гимназию, он изучал философию, право и математику во Львовском университете, ас 1814 гола преподавал математику в лицее. С 1826 года Кулик стал профессором высшей математики Пражского университета. Много сил ученый отдал развитию культуры, науки и образования в родном крае. Он подарил много книг галицким гимназиям и Львовскому университету. Кулик является автором многих научных работ, но в историю математики он вошел как непревзойденный вычислитель и составитель математических таблиц.

Разложение натуральных чисел на простые множители

Составное число 24 можно записать как произведение двух множителей, например, 24 = 6•4. Говорят, что число 24 разложили на два множителя — 6 и 4. Числа 6 и 4 тоже можно разложить на множители: 6 = 3•2; 4 = 2•2. Теперь число 24 можно записать так: 24 = 3 • 2 • 2 • 2. В произведении 3 • 2 • 2 • 2 все множители являются простыми числами. Итак, число 24 разложили на простые множители.

Разложить число на простые множители означает записать его в виде произведения простых чисел. Любое составное число можно разложить на простые множители. Например:

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

Пусть надо разложить на простые множители число 630.

Записываем это число и проводим справа вертикальную черту Наименьшим простым делителем этого числа является 2; записываем 2 справа or черты. Делим 630 на 2 и записываем частное 315 слева от черты под числом 630. Находим теперь наименьший простой делитель числа 315. Им является число 3, записываем его справа от черты. Делим 315 на 3, частное 105 записываем слева. Делим 105 на 3, получаем 35; 35 делим на 5, получаем 7. Число 7 простое, разделив его на 7, получим I. Разложение закончено.

Итак,

Пример:

Найти все делители числа 126.

Решение:

Разложим число 126 на простые множители:

Делителями числа 126 являются: 1, простые числа 2, 3, 7 в полученном разложении и всевозможные произведения чисел 2, 3, 3, 7, то есть:

И так, делителями числа 126 являются:

Запишем все делители в порядке их возрастания:

Интересные рассказы

Расположение простых чисел

Утверждение о том, что каждое отличное от 1 натуральное число можно записать в виде произведения простых множителей и притом единственным способом, если не принимать во внимание порядок расположения сомножителей, является так называемой основной теоремой арифметики — одной из древнейших математических наук (в переводе с греческого «арифметика» — «искусство чисел»).

В соответствии с основной теоремой арифметики простые числа являются как бы кирпичами, из которых «строятся» натуральные числа. Этим и объясняется внимание к простым числам со стороны математиков всех времен. Еще древнегреческий математик Эвклид (ок. 365 ок. 300 г. до н. э.) доказал, что простых чисел есть бесконечно много, поэтому наибольшего простого числа не существует. Но еще до сих пор не изучены закономерности расположения простых чисел в натуральном ряду.

Талантливые математики многих стран стремились найти закон расположения простых чисел.

В решении этого сложного вопроса весомый результат получил русский ученый, академик Пафнутий Львович Чебышев (1821 — 1894). Он доказал, что между любым натуральным числом больше 1 и его удвоением всегда существует хотя бы одно простое число.

О свойствах простых чисел выдвинуто много интересных гипотез. Среди них самой интересной является гипотеза члена Петербургской академии наук Кристиана Гольдбаха (1690 1764), сформулированная так: любое натуральное число больше 5 является суммой трёх простых чисел

Свойства простых чисел можно наглядно представить так:

• а) представим прямолинейный провод, выходящий из комнаты в мировое пространство, проходящий возле Луны и далее за огненный шар Солнца — в бесконечность;
• б) мысленно развесим на нем через каждый метр электрические лампочки и пронумеруем их натуральными числами;
• в) мысленно включим свет с таким расчетом, чтобы загорелись лампочки, номера которых являются простыми числами;
• г) мысленно полетим вдоль этого провода.

Перед нами откроется следующая картина.

1. Лампочка под номером 1 не горит, поскольку единица не является простым числом.
2. Две следующие лампочки под номерами 2 и 3 горят, поскольку числа 2 и 3 — простые. Больше таких лампочек, которые являются соседними и горят, мы не увидим.
3. Будем наблюдать пары лампочек, которые горят, соответствующие числам-близнецам (3 и 5, 5 и 7, 11 и 13 и т. д.). Самой большой из известных пар чисел-близнецов является 10 999 949 и 10 999 951.
4. Чем дальше будем лететь, тем будет становиться темнее, потому что реже будут гореть лампочки. А вот наступил большой промежуток темноты. Но мы вспоминаем свойство простых чисел, открытое Эвклидом, и смело движемся вперед, так как знаем, что впереди еще обязательно есть горящие лампочки, и их достаточно много.
5. Снова долго летим, а впереди и позади — темнота. Снова вспоминаем свойство простых чисел, доказанное Чебышевым, и следуем далее, уверенные в том, что, пролетев путь не больше того, который уже пролетели, мы обязательно увидим свет.

Наибольший общий делитель

Выпишите все делители чисел 18 и 24 и подчеркните их общие делители

Общими делителями (они подчеркнуты) чисел 18 и 24 являются числа 1, 2, 3, 6, наибольшим из них является 6. Число 6 является наибольшим натуральным числом, на которое делятся и 18, и 24.

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

Итак, наибольшим общим делителем чисел 18 и 24 являегся число 6. Сокращенно это записывают так: НОД( 18; 24) 6.

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

Рассмотрим еще один способ нахождения наибольшего общего делителя, взяв числа 210 и 294. Разложим каждое из этих чисел на простые множители:

Подчеркнем все общие простые множители в разложении данных чисел: 2, 3, 7. Числа 210 и 294 делятся на каждое из чисел 2, 3, 7 и на их произведение: 2•3•7 =42. Число 42 является наибольшим общим делителем чисел 210 и 294:

Назовите последовательность шагов при нахождении НОД двух чисел.

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

По такому правилу можно находить наибольший общий делитель трёх и более чисел. Найдем, например, наибольший общий делитель чисел 45, 75 и 90. Разложим эти числа на простые множители и подчеркнем общие для всех чисел множители:

Итак,

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

Два числа, наибольший общий делитель которых равен 1, называют взаимно простыми числами. Например, числа 16 и 27 являются взаимно простыми, так как их наибольшим общим делителем является 1.

Взаимно простые числа вообще имеют только один общий делитель — число 1. Поэтому, если два числа имеют общий делитель, отличный от 1, то они не взаимно простые. Например, числа 18 и 45 не являются взаимно простыми, так как имеют общий делитель 3.

• Заказать решение задач по высшей математике

Пример:

Какое наибольшее количество одинаковых букетов можно составить из 24 васильков и 32 ромашек, использовав все цветы?

Решение:

Из данных цветов можно, например, составить 2 букета. в каждом из которых будет 12 васильков и 16 ромашек. Нельзя составить три букета, так как 32 ромашки нельзя разделить на 3 одинаковые части. Можно составить четыре одинаковых букета, так как и 24 василька, и 32 ромашки можно разделить на 4 одинаковые части. Очевидно, что для решения задачи нужно найти наибольшее число, на которое можно разделить 24 василька и 32 ромашки, то есть найти наибольший общий делитель чисел 24 и 32. Поскольку НОД(24; 32) = 8, то можно составить самое большее 8 одинаковых букетов. Каждый такой букет будет состоять из 24 : 8 = 3 васильков и 32 : 8 = 4 ромашек.

Кратные натурального числа. Наименьшее общее кратное

Числа 36, 72, 180 делятся на 18. Говорят, что числа 36, 72, 180 кратны числу 18.

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

Все числа, кратные числу 18, можно получить, умножая число 18 последовательно на числа 1,2, 3,4, 5,….

18, 36, 54, 72, 90,… — числа, кратные 18.

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

Запишите числа, кратные 9. и числа, кратные 12, и подчеркните их общие кратные.

Общими кратными чисел 9 и 12 являются подчеркнутые числа 36, 72, …. Все они делятся на 9 и на 12. Наименьшим общим кратным является число 36

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

То, что наименьшим общим кратным чисел 9 и 12 является число 36, сокращенно записывают так: НОК(9; 12) = 36.

Разложим числа 9, 12 и их наименьшее общее кратное 36 на простые множители:

Мы видим, что разложение числа 36 можно получить, если разложение числа 9 умножить на 2 • 2. Числа 2 и 2 — это такие множители из разложения числа 12, которых нет в разложении числа 9

Назовите последовательность шагов при нахождении НОК двух чисел.

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

Найдем наименьшее общее кратное чисел 90 и 210.

Если одно из чисел делится на другое, то большее из них является наименьшим общим кратным этих чисел. Например, НОК(21; 63) = 63.

Наименьшим общим кратным двух взаимно простых чисел являегся произведение этих чисел. Например, НОК(8; 9) = 72.

Наименьшее общее кратное можно найти не только для двух, но и для трех и более чисел.

Например, для чисел 12, 18, 24 имеем:

Пример:

Найти наименьшее четырехзначное число, кратное 27.

Решение:

1000 — наименьшее четырехзначное число. Разделим его на 27: 1000: 27 = 37 (ост. 1).

27 • 38 = 1026 — наименьшее четырехзначное число, кратное 27.

Пример:

Шаг отца равен 72 см, а шаг сына — 54 см. Найти наименьшее расстояние, которое нужно пройти как отцу, так и сыну, чтобы каждый из них сделал при этом целое число шагов.

Решение:

Искомое расстояние в сантиметрах должно выражаться таким наименьшим числом, которое делится на 72 и на 54. Таким числом являемся наименьшее общее кратное этих чисел. Найдем НОК(54; 72):

Итак, искомое расстояние равно 216 см. На таком расстоянии отец сделает 216 : 72 = 3 шага, а сын — 216 : 54 = 4 шага.

Пример:

Найти наименьшее общее кратное чисел 15 и 12.

Решение:

Находим кратные большего из чисел и проверяем, делятся ли они на меньшее число: 15 не делится на 12; 15 • 2 = 30 — не делится на 12; 15 • 3 = 45 не делится на 12; 15 • 4 = 60 — делится на 12. Итак, НОК( 15; 12) = 60.

Памятка:

1. 24 = 6 • 4; 6 и 4 — делители числа 24
2. Число 210 делится на 10, так как заканчивается 0.
3. Числа 140 и 135 делятся на 5, так как заканчиваются 0 или 5
4. Числа 510, 512, 324, 126, 438 делятся на 2, так как заканчиваются однозначным четным числом.
5. Число 741 делится на 3; 7 + 4+1 = 12; 12:3 = 4, сумма цифр делится на 3. Число 711 делится на 9; 7+1 + 1=9; 9:9=1, сумма цифр делится на 9.
6. Число 17 делится только на 1 и 17; 17 — простое число; делителями являются 1 и само число.
7. Число 14 делится не только на I и 14, а и на 2; 14 — составное число; делителей больше двух.
8. НОД( 18; 24) = 6; 6 — наибольшее натуральное число, на которое делятся 18 и 24.
9. НОК(50; 75) =150; 150 — наименьшее натуральное число, которое делится на 50 и на 75.