Сколько существует чисел от 1 до 300 , которые не делятся ни на 5, 12 и 15

@BonaBerry · Регистрация: 21.09.2013

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

привет!
Задача звучит так "Сколько существует чисел от 1 до 300 , которые не делятся ни на 5, 12 и 15?"
Загвоздка в том что 15=5*3
Что мне делать с такими сочетаниями при подчете как 299/5*15 , 299/5 299/12*5
выкинуть?
Правильным будет такими результат:
299-(24+59+19) - 4-1+ 0=202
Развейти мои думки, пожалуйста

//прошу прощения за ошибку в заголовке темы

iifat · 04.12.2013, 16:30

Дааа, теорию чисел лучше получить

Основная (так, кажется) теорема — число однозначно представляется в виде произведения степеней простых чисел. Например,
$https://www.cyberforum.ru/cgi-bin/latex.cgi?\begin{tabular}[rcl]6&=&2^13^1\\12&=&2^23^1\\25&=&2^03^05^2\end{tabular}$
Ну-ка, сообрази: $https://www.cyberforum.ru/cgi-bin/latex.cgi?2205 (2^03^25^17^2)$ делится на $https://www.cyberforum.ru/cgi-bin/latex.cgi?35 (2^03^05^17^1)$ ? А в общем случае, имея разложения, как проверить делимость?

@BonaBerry · 04.12.2013, 16:51 **[ТС]**

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

Дааа, теорию чисел лучше получить

Основная (так, кажется) теорема — число однозначно представляется в виде произведения степеней простых чисел. Например,
$https://www.cyberforum.ru/cgi-bin/latex.cgi?\begin{tabular}[rcl]6&=&2^13^1\\12&=&2^23^1\\25&=&2^03^05^2\end{tabular}$
Ну-ка, сообрази: $https://www.cyberforum.ru/cgi-bin/latex.cgi?2205 (2^03^25^17^2)$ делится на $https://www.cyberforum.ru/cgi-bin/latex.cgi?35 (2^03^05^17^1)$ ? А в общем случае, имея разложения, как проверить делимость?

ИУ!!!

Разложить число на множители, что ли!?
Вот так:
30=6*5= 2*3*5
30=15*2=5*3*2
И если все большие циферки одинаковые - танцуй и радуйся, у этих чисел много общего как оказывается!

P.S. Часов так через 6-7 напишу решение, той задачи, которую сама здесь задавала. И пока пошла ~~учиться~~, думать.
А теперь вопрос от меня:"Какова вероятность наличия светлого пигмента в моих волосах?. Если волосы у меня длинные."

@Heidegger · 04.12.2013, 16:59

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

@BonaBerry · 05.12.2013, 11:17 **[ТС]**

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

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

я понимаю это непосредственно подсказка к моему почему, что то учитывается а что-то нет.

И так "та-да-да-там" решение задачи:
Задача.
Сколько чисел от 1 до 300, которые не делятся ни на 15, ни 5, ни на 12?
Решение:
1. Находим количество чисел, которые делятся.
на 5: 300/5=60
на 12: 300/12=25
на 15: 300/15=20
2.Находим количество чисел которые делятся:
на 5 и 12: 300/5*12=5
на 12 и 15: 300/12*15=1
на 5 и 15: 300/5*15=4
Так как:
12=6*2*3*1
15=5*3*1
5=5*1
Становится видно, что множество чисел, которые делятся на 15 входят в множество тех чи
сел, которые делятся на 5.
Поэтому где фигурирует 15, нам не нужно, и в подсчет берем только 5 и 12.
Это значит так:
60+25-5=80 - количество чисел, которые делятся.
300-80=220 -количество чисел которые не делятся ни на 5, ни 12, ни на 15.
Как-то так. Как?

@Heidegger · 05.12.2013, 12:38

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

я понимаю это непосредственно подсказка к моему почему, что то учитывается а что-то нет.

Да, именно.

d = НОД(a; b) – это наибольшая "общая часть" чисел a и b (т.е. наибольшая "плитка", которой можно их выложить), и каждое из чисел кратно их совместному НОД: a = m∙d, b = n∙d. Поэтому если какое-то число не делится на НОД(a; b), то оно не делится и на каждое из них. И именно поэтому в данной задаче число 15 можно отбросить: НОД(5; 15) = НОД(5; 3∙5) = 5 совпадает с первым числом, и всё, что не делится на 5, не делится также и на 15, т.е. число 15 в условии задачи действительно лишнее. Это первый момент.

Второе: c = НОК(a; b) – это самый маленький "ящик", который можно плотно выложить с помощью a или b, и НОК кратен каждому из чисел: c = m∙a, c = n∙b. Поэтому если какое-то число делится на НОК(a; b), то оно делится и на каждое из них. И поэтому, чтобы найти количество чисел от 1 до n, которые делятся на a и b, необходимо найти целую часть от деления n на c = НОК(a; b): k = [n/c].

Если числа a и b взаимно простые (не имеют общих делителей), то их НОК равен их произведению: c = НОК(a; b) = a∙b.

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

Находим количество чисел которые делятся:
на 5 и 12: 300/5*12=5

Здесь верно: НОК(5; 12) = НОК(5; 2²∙3) = 5∙2²∙3 = 5∙12 и 300/НОК(5; 12) = 300/5∙12 = 5.

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

на 12 и 15: 300/12*15=1
на 5 и 15: 300/5*15=4

А вот здесь уже неверно. Если бы в исходном задании были только числа 12 и 15, сколько бы получилось?

@BonaBerry · 06.12.2013, 12:03 **[ТС]**

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

Да, именно.

d = НОД(a; b) – это наибольшая "общая часть" чисел a и b (т.е. наибольшая "плитка", которой можно их выложить), и каждое из чисел кратно их совместному НОД: a = m∙d, b = n∙d. Поэтому если какое-то число не делится на НОД(a; b), то оно не делится и на каждое из них. И именно поэтому в данной задаче число 15 можно отбросить: НОД(5; 15) = НОД(5; 3∙5) = 5 совпадает с первым числом, и всё, что не делится на 5, не делится также и на 15, т.е. число 15 в условии задачи действительно лишнее. Это первый момент.

Второе: c = НОК(a; b) – это самый маленький "ящик", который можно плотно выложить с помощью a или b, и НОК кратен каждому из чисел: c = m∙a, c = n∙b. Поэтому если какое-то число делится на НОК(a; b), то оно делится и на каждое из них. И поэтому, чтобы найти количество чисел от 1 до n, которые делятся на a и b, необходимо найти целую часть от деления n на c = НОК(a; b): k = [n/c].

Если числа a и b взаимно простые (не имеют общих делителей), то их НОК равен их произведению: c = НОК(a; b) = a∙b.
Здесь верно: НОК(5; 12) = НОК(5; 2²∙3) = 5∙2²∙3 = 5∙12 и 300/НОК(5; 12) = 300/5∙12 = 5.

А вот здесь уже неверно. Если бы в исходном задании были только числа 12 и 15, сколько бы получилось?

Спасибо! Извиняюсь за поздний комментарий.
Увидела ошибку.
НОК (12, 15)=60 так как:
К 12(24, 36, 48,б0..)
К 15 (15,30,45, 60...)
Далее 300/60=5
И получается 300 -(5+25)+5=275

iifat · 06.12.2013, 14:16

А теперь всё сначала и аккуратнее

Или я задачу забыл? От одного до трёхсот, не делятся ни на 5, ни на 12, ни на 15 — так? Тогда ты где-то запуталась. Хотя с пониманием наибольшего общего кратного — поздравляю.

@BonaBerry · 09.12.2013, 11:01 **[ТС]**

Я подумала что, до меня может дойти уверенное решение этой задачи за выходные, как до утки на третьи сутки, ну, или решение других задач осенит меня (в хорошем смысле) и я буду со 100% уверенностью вещать вернее решение задачи.
Ну, ну...
Поэтому начну опять, а вы уж потерпите)))
На 5: 300/5=60
на 12: 300/15=25
15 подмножество 5ти его не надо брать.
на 12 и 5 одновременно: 300/60 (этоНОК12 и 5) = 5
Ищем сколько чисел от 1 до 300 можно разделить и на 5(как и на 15) и 12 без остатка: 60+25-5=80

И теперь вычетам из 300-80=220 не делятся ни на 5 (ни на 15) ни на 12.
Занавес

@Heidegger · 09.12.2013, 12:32

Да, теперь всё верно. Чтобы придать ещё больше уверенности (надеюсь), можно добавить, что удаление 15 из списка чисел сокращает объём вычислений, но общая формула будет работать и в том случае, если 15 останется:

Matlab M
1
2
3
4
5
6
7
n = 300; F[k_] := Floor[n/k];
 
n - (F[5] + F[12]) + F[LCM[5, 12]]
> 220
 
n - (F[5] + F[12] + F[15]) + (F[LCM[5, 12]] + F[LCM[5, 15]] + F[LCM[12, 15]]) - F[LCM[5, 12, 15]]
> 220

Это проверочный код в Mathematica. Здесь LCM – это НОК (least common multiple), F[k] – целая часть от деления n = 300 на k.
Можно проверить результат, вычислив его по полной формуле, и бонусом дорешать похожую задачу: Сколько натуральных чисел от 1 до 10000
Способность решить задачу более чем одним способом всегда повышает уверенность в собственных силах. :)

@BonaBerry · 09.12.2013, 13:23 **[ТС]**

Так так, так столько танцев с бубном!!!
А тут можно и так оказывается,зато столько много нового узнала)))
Разрешите, проверю, краисвым финалом.
300-(60+25+20)+5++5+20-5=300-105+25=220 и правда

Всем огромное спасибо кто ПОМОГАЛ, читал теиу и руаал!
Все на самом деле стало ясно почему и для чего НОД и НОК (с ними невероятно удобно), почему 15 является подмножеством 5.
Впереди еще лист с заданиями (немного уже решины), так что действительно буду рада и благодарна за помощь как сейчас

Новые блоги и статьи Все статьи Все блоги /
Нейросеть на алгоритме "эстафета хвоста" как перспектива. Hrethgir 06.05.2026 На десерт, когда запущу сервер. Статья тут https:/ / habr. com/ ru/ articles/ 1030914/ . Автор я сам, нейросеть только помогает в вопросах которые мне не известны - не знаю людей которые знали-бы. . .	Асинхронный приём данных из COM-порта Argus19 01.05.2026 Асинхронный приём данных из COM-порта Купил на aliexpress термопринтер QR701. Он оказался странным. Поключил к Arduino Nano. Был очень удивлён. Наотрез отказывается печатать русские буквы. Чтобы. . .	попытка написать игровой сервер на C++ pyirrlicht 29.04.2026 попытка написать игровой сервер на плюсах с открытым бесконечным миром. возможно получится прикрутить интерпретатор питон для кастомизации игровой логики. что есть на текущий момент:. . .	Контроль уникальности выбранного документа-основания при изменении реквизита Maks 28.04.2026 Алгоритм из решения ниже разработан на примере нетипового документа "ЗаявкаНаРемонтСпецтехники", разработанного в КА2. Задача: уведомлять пользователя, если указанная заявка (документ-основание). . .
Благородство как наказание Maks 24.04.2026 У хорошего человека отношения с женщинами всегда складываются трудно. А я человек хороший. Заявляю без тени смущения, потому что гордиться тут нечем. От хорошего человека ждут соответствующего. . .	Валидация и контроль данных табличной части документа перед записью Maks 22.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа, разработанного в КА2. Задача: контроль и валидация данных табличной части документа перед записью с учетом регламента компании. . .	Отчёт о затраченных материалах за определенный период с макетом печатной формы Maks 21.04.2026 Отчёт из решения ниже размещён в конфигурации КА2. Задача: разработка отчёта по затраченным материалам за определённый период, с возможностью вывода печатной формы отчёта с шапкой и подвалом. В. . .	Отчёт о спецтехнике находящейся в ремонте Maks 20.04.2026 Отчёт из решения ниже размещен в конфигурации КА2. Задача: отобразить спецтехнику, которая на данный момент находится в ремонте. Есть нетиповой документ "Заявка на ремонт спецтехники" который. . .

@BonaBerry 3 / 3 / 0 Регистрация: 21.09.2013 Сообщений: 73

	Сколько существует чисел от 1 до 300 , которые не делятся ни на 5, 12 и 15 01.12.2013, 02:47. Показов 16169. Ответов 29 Метки нет (Все метки) привет! Задача звучит так "Сколько существует чисел от 1 до 300 , которые не делятся ни на 5, 12 и 15?" Загвоздка в том что 15=53 Что мне делать с такими сочетаниями при подчете как 299/515 , 299/5 299/12*5 выкинуть? Правильным будет такими результат: 299-(24+59+19) - 4-1+ 0=202 Развейти мои думки, пожалуйста //прошу прощения за ошибку в заголовке темы 0

iifat 2910 / 1941 / 213 Регистрация: 05.06.2011 Сообщений: 5,736
	04.12.2013, 16:30
	Дааа, теорию чисел лучше получить Основная (так, кажется) теорема — число однозначно представляется в виде произведения степеней простых чисел. Например, $https://www.cyberforum.ru/cgi-bin/latex.cgi?\begin{tabular}[rcl]6&=&2^13^1\\12&=&2^23^1\\25&=&2^03^05^2\end{tabular}$ Ну-ка, сообрази: $https://www.cyberforum.ru/cgi-bin/latex.cgi?2205 (2^03^25^17^2)$ делится на $https://www.cyberforum.ru/cgi-bin/latex.cgi?35 (2^03^05^17^1)$ ? А в общем случае, имея разложения, как проверить делимость? 0

@Heidegger 617 / 242 / 16 Регистрация: 31.07.2013 Сообщений: 376
	04.12.2013, 16:59
	Чтобы легче думалось: основные понятия, которые понадобятся при решении этой задачи – это НОД и НОК. 0

iifat 2910 / 1941 / 213 Регистрация: 05.06.2011 Сообщений: 5,736
	06.12.2013, 14:16
	А теперь всё сначала и аккуратнее Или я задачу забыл? От одного до трёхсот, не делятся ни на 5, ни на 12, ни на 15 — так? Тогда ты где-то запуталась. Хотя с пониманием наибольшего общего кратного — поздравляю. 0

@BonaBerry 3 / 3 / 0 Регистрация: 21.09.2013 Сообщений: 73
	09.12.2013, 11:01 [ТС]
	Я подумала что, до меня может дойти уверенное решение этой задачи за выходные, как до утки на третьи сутки, ну, или решение других задач осенит меня (в хорошем смысле) и я буду со 100% уверенностью вещать вернее решение задачи. Ну, ну... Поэтому начну опять, а вы уж потерпите))) На 5: 300/5=60 на 12: 300/15=25 15 подмножество 5ти его не надо брать. на 12 и 5 одновременно: 300/60 (этоНОК12 и 5) = 5 Ищем сколько чисел от 1 до 300 можно разделить и на 5(как и на 15) и 12 без остатка: 60+25-5=80 И теперь вычетам из 300-80=220 не делятся ни на 5 (ни на 15) ни на 12. Занавес 0

@BonaBerry 3 / 3 / 0 Регистрация: 21.09.2013 Сообщений: 73
	09.12.2013, 13:23 [ТС]
	Так так, так столько танцев с бубном!!! А тут можно и так оказывается,зато столько много нового узнала))) Разрешите, проверю, краисвым финалом. 300-(60+25+20)+5++5+20-5=300-105+25=220 и правда Всем огромное спасибо кто ПОМОГАЛ, читал теиу и руаал! Все на самом деле стало ясно почему и для чего НОД и НОК (с ними невероятно удобно), почему 15 является подмножеством 5. Впереди еще лист с заданиями (немного уже решины), так что действительно буду рада и благодарна за помощь как сейчас 0