Понравилась задачка по программированию/математике. Из тех, что первокурсникам-программистам дают. Нашел элегантное решение и радуюсь. Может, надо было в программисты идти? :))
"Напишите функцию, которая найдет самое маленькое число, которое делится нацело на все числа от 1 до N (N<40, вводится пользователем)"

я таких мозгодробилок(для меня иначе и не назовешь) на питоне штук 40 нарешал )

(1) Млдц!

(0) Я за тебя тоже радуюсь.

(3) Дык! За такого красавчика грех не порадоваться! Затем и поделился!

А мне грустно, потому что вспоминил школу и уроки информатики в 5-ом классе...

(4) ну, выкладывай, потестируем

(0)
> Может, надо было в программисты идти?
поздно ((

(6) Шиш тебе! Сам любоваться буду!
Хочешь и себе такую лапочку - сам пиши!
(7) Отож :(

(8) ок. не хочу я эту лапочку. Просто можно было проверить. Наверняка какую-то бредятину ведь написал, и радуешься.

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

(0)Так вроде всё просто.
r := n;
для ш := 2 до n-1 цикл
Если r mod ш <> 0 То
   r := r * ш;
КонецЕсли;
КонецЦикла;
За смесь языком простите.

(10) самое простейшее решение, нашел за одну минуту

Массив = Новый Массив;
Массив.Добавить(1);
Массив.Добавить(2);
Массив.Добавить(6);
Массив.Добавить(12);
Массив.Добавить(60);

...

Возврат Массив[N-1];

это же НОК.
НОК = П / НОД

НОД находится алгоритмом Эвклида

Для проверки: для N = 10 ответ 2520

(13) Молодец! Только если в лоб через НОД решать для нескольких чисел, решение будет не шибко элегантным.

(15) а если N = 40 000 000, сколько получается?

(17) Очевидно же: "вы ввели некорректные данные, попробуйте снова"

(11) Это не самое маленькое будет
(17) В нашей вселенной такие числа не нужны

(16) нужно вначале просеять чилса

ну или с конца идти, тогда попроще будет находить

(15) а 1260 не подойдёт?

(22) на 8 не делится)

(0) до 40 слишком банально: раскладываем по степеням простых чисел и берем максимальные степени

(19)Какие Ваши доказательства?(с)

Ограничение в N<40, как я понял, спецом подобрано чтобы результат в 64 бита влез. Т.е. в стандартные целочисленные типы данных.

(25) для 4 проверь

(15) 2520 и на калькуляторе посчитать интуитивно можно, ты разложением проверял?

Рекурсией легко.
Произведение чисел от 1 до N-1, при удалении всех делителей других чисел.

Например для N=10
1*2*3*4 и тут надо удалить 2 или можно поделить на 2
1*3*4*5*6 и тут надо удалить 3, так то еще и 2 но 2 мы уже удалили
1*4*5*6*7*8 удаляем 4
1*5*6*7*8*9 = ?

(28) Такой пример прям в условии задачи был.

(29) У 6 и 9 общие делители - явно неверно

(27)12 получилось.
Возможно ты и прав. Но тут либо контрпимер нужен, либо математическое обоснование.

(32) Математическое обоснование в (13) указано

П(p[i]^Цел(log(N,p[i]))

П - произведение
p - массив простых чисел до N
log(a, b) - логарифм a по b

(33)А кто сказал, что у меня не НОК в результате получится?

(35) ты же на 4 проверил? это и есть контрпример

(36)на 4 у меня получилось. На 5 - нет.

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

(37) Да у тебя странное решение. Взять N, а потом цикл от 2 до N-1. Простой (убывающий) цикл от N до 2 дал бы правильный ответ

(31) Да ты прав, надо еще на 2 и на 3 поделить ибо 6 и 8 а так же 6 и 9

(40)+ Тогда это просто произведение всех простых чисел от 1 до N-1

(41) нет,  оно не делится на степени простых чисел больше единицы.

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

(42) Ага тогда (34) самое простое

(43) + Вернее, не то чтобы отсев... Просто получилось в одном простом алгоритме красиво совместить и разложение на множители и учет "новых" множителей за один проход и минимальное использование памяти.

(44) теоретически "простое" и обоснованное - да (34)

(44) (45) На практике самое банальное это (11) только с обратным циклом от N до 2. Проще не придумаешь.

(45) Код будет?

(46) а не, обратный цикл похоже не работает

Можно так.
рез = 1;
Для ш = 2 По N Цикл
   Если рез % ш = 0 Тогда
      Продложить;
   КонецЕсли;
   т = 1;
   Пока т <= N Цикл
      т = т * ш;
   КонецЦикла;
   т = т / ш;
   рез = рез * т;
КонецЦикла

(49) похоже на правильное

Академические задачки, бессмысленные и беспощадные...

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

(47) Не. После (34) это детский лепет. Теперь я стесняюся :)
Но правда же, прикольная задачка?

(51) Нифига не бессмысленные. Есть много вариантов решения и чем сильнее ты прошаренный, тем эффективнее сможешь решить.
Это тебе не "Если СуперБизнесУсловиеВыполняется Тогда СуперБизнесФичаПрименяется"

(53) В задаче реализации математической формулы - нет ничего прикольного.

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

(55) В реализации - нет. В выведении - есть. Я поэтому и писал программирование/математика, а не чисто программирование.

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

Так что может и не зря я в программисты не пошел :)

Интересные задачи на применение игровых методов и Монте-Карло

(59) Чем больше исследовательская составляющая - тем интереснее. Ясен пень.

(50)Это та же идея, что у тебя в (34) только без логарифмов и просеивание простых чисел "на лету".
Математически это произведение степеней простых чисел, не превышающих N.

(61) Так и есть. В (49) реализация (34). Работоспособность не проверял, но на первый взгляд оно и есть.

(34) Слушай, а дай свой ход умозаключений, как ты до этого быстро додумался? Я, что называется, "глазами" понимаю как это работает исходя из существующей закономерности, но видно туплю и простой логической цепочки в голове не складывается. А ты ведь как-то сразу сообразил.

(63) Погуглить самостоятельно решения НОД / НОК никак?

(64) Про НОД и НОК я в курсе в целом. Видимо у меня проблема сложить два и два. Подадите убогому?

(63) смотри (24). В (34) просто формализация.

(66) Да это понятно :) Непонятно формальное доказательство того, что (24) - решение. Видимо я жестко туплю.

(67) Даже не знаю, где у тебя сомнения.
Непростые множители не рассматриваем вроде очевидно.
Максимальные степени делятся на меньшие - достаточность очевидна.
Меньшие степени не делятся на максимальные - необходимость.

(68) Сомнений нет. Я все это понимаю, глядя на закономерность разложения ряда чисел на простые множители. Но как ты это сразу сообразил - для меня непостижимо :) Решил - а вдруг ты сможешь научить меня правильно думать? :)

(69)Это математика. Задачу можно доказать либо с помощью математической индукции, либо как следствие основной теоремы арифметики (об однозначном разложении натурального числа на простые множители).
Вывод учи матчасть(математику).

(70) Ну, с индукцией ясно. А докажи-ка, как знающий матчасть, как следствие основной теоремы арифметики.

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

(72)ОТА утверждает, что разложение натурального числа на простые множители единственно с точностью до порядка следования степеней. То есть наше произведение можно представить в виде:
p1^i1*...*pk^ik. Где p1=2, а pk не превосходит квадратного корня из N(что в условии задачи).
И любой сомножитель будет иметь такой же вид, только степени будут не больше, чем в произведении.
Так как степени простых чисел у нас будут "по умолчанию"(мы составляем сомножители из них), то остаётся рассмотреть составные числа. В разложении таких чисел также участвовуют степени простых чисел, которые мы уже рассматривали ранее. Остаётся только показать, что степени простых чисел, которые мы уже "отправили" в результат не меньше, чем в текущем числе. Это очевидным образом следует из того, что если степень в проверяемом числе будет больше, то простое число в этой степени будет больше N, что не может быть, так как мы брали максимальную степень, не превышающую N. (И если её умножить на большее простое число, то произведение будет явно больше N.)

(73) "а pk не превосходит квадратного корня из N"
На ход рассуждений конечно не влияет, но pk <= N.

(74)Спутал с разложением на множители.

(75)Точнее с условием простоты числа.