Версия для печати темы

Автор: Сергей Меркурьев 24.05.2009 21:26

Задано натуральное число N. Требуется написать программу, которая находит количество натуральных чисел, не превышающих N и не делящихся ни на одно из чисел 2, 3, 5.
Ограничения 1 <= N <= 10^9

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

Автор: amega 24.05.2009 22:31

проходить в цикле и проверять условие

j:=0;
for i:=1 to n do
 if (i mod 2 <> 0) and (i mod 3 <> 0) and (i mod 5 <> 0) then inc(j);

Автор: Сергей Меркурьев 24.05.2009 22:52

Я же ведь говорю что глупым перебором задачу глупо решать!!! Возьмите у себя число 1 000 000 и посмотрите как долго она прокручиваться будет!

Я бы хотел более быстрым методом сделать...

Автор: volvo 24.05.2009 23:22

Сергей Меркурьев, а не надо считать все подряд

Можешь воспользоваться тем фактом, что в каждой тридцатке чисел, тех чисел, которые тебя устраивают (не делящихся на 2, 3 или 5) ровно 8 штук: 1, 7, 11, 13, 17, 19, 23, 29... То есть,

  j := 8*(N div 30);
  for i := 1 to (N mod 30) do
    if (i mod 2 <> 0) and (i mod 3 <> 0) and (i mod 5 <> 0) then inc(j);
  writeln(j);

Выдаст тебе результат мгновенно...

Автор: Сергей Меркурьев 24.05.2009 23:28

Действительно!! А я то тут мудрил искал закономерность совсем в другом))) Оказалось всё так просто)) Спасибо!

Слушайте, а может быть ещё какое-нибудь решение данной задачи?

Автор: volvo 24.05.2009 23:45

Более быстрое - вряд ли, хотя можно забить эти 8 чисел в массив и проверять на сами числа, без деления на 2, 3, 5. Но насколько это ускорит алгоритм? Мелочи... Или речь о совершенно других решениях (кроме перебора)?

Автор: Сергей Меркурьев 24.05.2009 23:50

Да в принципе это практически ничего не даст... Ещё раз спасибо.

Автор: amega 25.05.2009 0:16

можно если знать матиматику, можно разложить в ряд и ккто попробывать реализовать формулу которая бы считала елементы...

Автор: Сергей Меркурьев 25.05.2009 10:30

Мне кажется что формулой считать бессмысленно так, как тут то и не найти такой закономерности))

Если учитывать что почти в каждой десятке (может через один, может через два) встречаются на конце чисел вот такие цифры - 1 3 7 9...
Но во многих десятках встречается только 1 и 7 или 3 и 9... Так что (как мне кажется) формулу выводить здесь сложно...

Автор: Lapp 25.05.2009 15:24

amega, открой секрет, что именно ты хотел раскладывать в ряд? и что за элементы считать? ))

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

Автор: Сергей Меркурьев 25.05.2009 23:27

В принципе всем спасибо за помощь)

Автор: Гость 12.03.2021 14:22

гомосеки