Тест простоты

[nikvic]

Gts в сообщении #823394 писал(а):

$N = d_1 \cdot d_2$, причем $d_1 \leqslant d_2$

Представьте второй сомножитель как сумму первого и неотрицательного числа.

[Nemiroff]

Gts в сообщении #823394 писал(а):

Меньший делитель будет меньше или равен квадратному корню произведения делителей.

Ну а если он больше?

[ewert]

Gts в сообщении #823394 писал(а):

Вот этот факт я хочу понять/доказать.

Т.е. Вы хотите доказать, что из $d_1 \leqslant d_2$ следует $d_1^2 \leqslant d_1 \cdot d_2$. И ничего не выходит, да?

[Gts]

Цитата:

Т.е. Вы хотите доказать, что из $d_1 \leqslant d_2$ следует $d_1^2 \leqslant d_1 \cdot d_2$. И ничего не выходит, да?

Ой... я этого не заметил. :)


Позвольте, я теперь разберусь с ответами других.

Цитата:

Представьте второй сомножитель как сумму первого и неотрицательного числа.

$N = d_1 \cdot d_2$
$d_1 \cdot (d_1 + k)$, где $d_1 = d_2 - k$ и $k > 0$
Только дальше я не вижу куда двигаться.

Цитата:

Ну а если он больше?

И Ваш подвод к ответу мне не понятен.

[Nemiroff]

Gts в сообщении #823410 писал(а):

И Ваш подвод к ответу мне не понятен.

Ну если один сомножитель больше, и второй тоже больше, то произведение?

[Gts]

Цитата:

Ну если один сомножитель больше, и второй тоже больше, то произведение?

То и произведение увеличится... Все еще не понял в чем суть.

[ИСН]

Что значит "увеличится"? В вопросе ничего не говорилось ни о каких изменениях. "Движенья нет, сказал мудрец брадатый."

-- менее минуты назад --

Вы следите за ними, за словами. Их можно класть друг на друга почти как угодно, но всё-таки не совсем. У них есть этот, как его, смысл. Он выскакивает и кусается.

[_Ivana]

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

[Gts]

Моя цитата:

Цитата:

Меньший делитель будет меньше или равен квадратному корню произведения делителей. $d_1 \leqslant \sqrt{d_1 \cdot d_2}$

Nemiroff предлагает "Ну а если он больше?" и "Ну если один сомножитель больше, и второй тоже больше, то произведение?"

Цитата:

Что значит "увеличится"? В вопросе ничего не говорилось ни о каких изменениях.

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

Цитата:

бежали по всем натуральным числам, меньшим самого числа, проверяя отсутствие делимости нацело.

Полный перебор. Это понятно.

Цитата:

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

Да, так как четные числа - есть составные числа.

Цитата:

можно бежать только до половины числа

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

В целом хочу сказать: меня уже ткнули в то, что я не увидел очевидного "Т.е. Вы хотите доказать, что из $d_1 \leqslant d_2$ следует $d_1^2 \leqslant d_1 \cdot d_2$. И ничего не выходит, да?"
Но мне кажется, все, кто мне помогает, видят решение по другому, не алгебраически, а лишь с помощью рассуждений.

[VAL]

Полагаю, тут происходит кормление тролля.
Но вдруг ТС искренне тормозит. Тогда попробую такой шаг:
Может ли получится положительное число $a$ при сложении двух положительных чисел, каждое из которых больше половины $a$?

[Gts]

Цитата:

Полагаю, тут происходит кормление тролля.

Честное слово: ну не понимаю я, торможу, как хотите назовите. У меня только одно желание: разобраться в этом вопросе.

Цитата:

Может ли получится положительное число $a$ при сложении двух положительных чисел, каждое из которых больше половины $a$?

Нет, не может. Если бы слагаемые были ровно $\frac a 2$, то мы бы получили $a$. А если слагаемые больше, то мы получим число большее $a$.

[VAL]

Gts в сообщении #823800 писал(а):

Цитата:

Может ли получится положительное число $a$ при сложении двух положительных чисел, каждое из которых больше половины $a$?

Нет, не может. Если бы слагаемые были ровно $\frac a 2$, то мы бы получили $a$. А если слагаемые больше, то мы получим число большее $a$.

Отлично!
А теперь вместо слагаемых возьмите два сомножителя, каждый из которых больше корня из $a$. Может ли при их перемножении получиться $a$?

[Nemiroff]

Gts в сообщении #823740 писал(а):

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

Тогда я не могу вам помочь.

[Gts]

Цитата:

возьмите два сомножителя, каждый из которых больше корня из $a$. Может ли при их перемножении получиться $a$?

Опять же нет. Получится число большее $a$. Если бы было два множителя равных $\sqrt{a}$, то произведение было бы $a$.

[VAL]

Gts в сообщении #823986 писал(а):

Цитата:

возьмите два сомножителя, каждый из которых больше корня из $a$. Может ли при их перемножении получиться $a$?

Опять же нет. Получится число большее $a$. Если бы было два множителя равных $\sqrt{a}$, то произведение было бы $a$.

Совершенно верно.
Поэтому и проверять множители имеет смысл только до корня из $a$.