Простые числа.

[wcl.AleX]

Способ даёт возможность узнать делится ли это число на 2 или 3 и всё.
Так как простые числа, кроме 2 и 3 не делятся на 2 или 3 то все проверяемые на простоту числа должны пройти этот тест.
Он является необходимым , но не достаточным условием простоты

По поводу отсутствия формулы простых чисел, то я её уже давно нашёл , просто пока не знаю, что с ней делать. Если интересно посмотрите Мой топик topic30901.html

[Gem]

[quote="wcl.AleX в сообщении #311901"]Если интересно посмотрите Мой топик topic30901.html[/quot]
Интересно.
Представляйте формулу сюда.
Если она верна(уж позвольте иметь мне по этому поводу своё мнение), это будет величайшее достижение человеческой мысли.
Формулу-в студию, плз.

[Gem]

Батороев в сообщении #311671 писал(а):

Покажите на конкретном примере, как Вы видите такую проверку?

Приношу извинения за вынужденное молчание.
Суть вот в чём
Пусть $2n+1=ab$
Сделаем замену
$b=a-2c$
Тогда
$2n+1=a^2-2ac$
Решим относительно $a$
Получаем
$a=c\pm\sqrt{c^2+2n+1}$
Для начала пусть
$c=o
Тогда
$a= scrt [2n+1]$
Увеличиваем полученное число до ближайшего целого.
Извлекаем корень.
Если он не целый, увеличиваем $c$ на единицу и продолжаем вычисление по этому алгоритму до тех пор, пока не получим решение в целых числах.
Пример.
Имеем число $9541$
Корень из него равен $97,678$
Увеличиваем до $98$
Получаем нецелочисленное решение.
Увеличиваем до$99$
На числе $125$ получаем целочисленное решение.

Если возникнут вопросы, буду рад на них ответить.

[venco]

Gem, а вы оценивали вычислительную сложность этого алгоритма?

[Gem]

venco в сообщении #312776 писал(а):

Gem, а вы оценивали вычислительную сложность этого алгоритма?

Разумеется.
Если угодно, давайте сравним с ситом Эратосфена..
Только нет смысла:я не сделал ничего нового.
Оказывается, это "всего лишь" метод Ферма.
Хотя, тем не менее, обсудить есть что.

[venco]

Gem в сообщении #312842 писал(а):

Только нет смысла:я не сделал ничего нового.
Оказывается, это "всего лишь" метод Ферма.

Именно. Этот метод по скорости уступает даже примитивному делению на все последовательные натуральные числа до $\sqrt n$.

[Gem]

venco в сообщении #312847 писал(а):

Именно. Этот метод по скорости уступает даже примитивному делению на все последовательные натуральные числа до .

Полноте.;)
Сколько действий(итераций?) будет по Вашему методу?
По моему-27.
У Вас?

[venco]

Ну, по "моему" методу - 24. Только какое отношение имеют конкретные числа к вычислительной сложности алгоритма?
А то ведь у меня есть ещё один метод: возьмём случайное число, например 47, попробуем разделить 9541 на 47. Делится! Итого - одна итерация.

[Gem]

venco в сообщении #312907 писал(а):

Ну, по "моему" методу - 24.

Покажите, плз, "Ваш" метод.
Свой я всё-таки показал.
Так что не оставайтесь в долгу.

venco в сообщении #312907 писал(а):

А то ведь у меня есть ещё один метод: возьмём случайное число, например 47, попробуем разделить 9541 на 47. Делится! Итого - одна итерация.

Я полагал, что Вы понимаете разницу между случайным подбором числа и его вычислением.
Быть может, просто в запале передёргиваете?

[Батороев]

Gem
Метод Ферма еще где-то можно использовать для факторизации чисел, но уж для проверки чисел на простоту он не совсем годится.
Чтоб убедиться, проверьте этим методом, к примеру, простоту числа $9543$.

[Gem]

Батороев в сообщении #313099 писал(а):

но уж для проверки чисел на простоту он не совсем годится.

Если правильно Вас понял, Вы предлагаете проверить на простоту простое число.
Разумеется, в этом случае придётся применить сито Эратосфена и ничего нового я не предложил.
Но я и не собирался этого делать.
Я всего лишь предложил метод разложения составного числа на множители.
Что до меня давно сделал Ферма.
Но.
Здесь форум для обсуждения и развития некоторых идей.
Вас сие не интересует?
Я хочу сказать, что есть у меня некоторые размышления, которые хотелось бы просто и спокойно обсудить.
Без претензий и заявлений.

[Батороев]

Число $9543$ - составное.

-- Вс апр 25, 2010 16:28:49 --

Уж, кто-кто, а я люблю такие вопросы обсуждать!
Наоборот, мне показалось, что Вы чего-то напрягаетесь.
Вам venco и я пытаемся лишь объяснить, что метод Ферма не очень эффективный.
Вы спрашивали, откуда у venco взялись 24 действия?
По-видимому, он занят и ответить не смог.
Объясняю: количество нечетных простых, не превышающих $\sqrt {9541}=97,68$, равно $24$.
Решето Эратосфена предполагает проверить делимость числа на эти простые.
Но это соотношение действий по двум методам - при довольно удобном числе.

На числе $9543$ количество действий будет далеко не в пользу метода Ферма.

[Gem]

Gem в сообщении #313116 писал(а):

Уж, кто-кто, а я люблю такие вопросы обсуждать!

Очень рад.

Батороев в сообщении #313132 писал(а):

Наоборот, мне показалось, что Вы чего-то напрягаетесь.

Именно показалось.
(скромно)У меня всё есть.
Для скромной жизни.

Батороев в сообщении #313132 писал(а):

Вам venco и я пытаемся лишь объяснить, что метод Ферма не очень эффективный.

Надо полагать, что с тех пор, как метод предложил Ферма, прошло немало времени.
В продолжении которого математики не сидели сложа руки.

Батороев в сообщении #313132 писал(а):

По-видимому, он занят и ответить не смог.

Скорее всего, принял меня за "упёртого" и решил не отвечать.
В силу бесполезности.
Напрасно.
Я всего лишь хотел бы обсудить некоторые идеи.
Вполне возможно, они бредовые-но как без эрудированных собеседников выяснить это?

Батороев в сообщении #313132 писал(а):

Объясняю: количество нечетных простых, не превышающих , равно .
Решето Эратосфена предполагает проверить делимость числа на эти простые.

Вы полагаете, в этом случае будет меньше итераций?
Как найти все простые без итераций?
Или Вы предлагаете по справочнику?

Батороев в сообщении #313132 писал(а):

На числе количество действий будет далеко не в пользу метода Ферма.

Благодарю за интересную задачку.
На досуге позабавляюсь.
Но ещё раз:как Вы найдёте все указанные Вами простые?
Без итераций, естественно.

[venco]

Gem в сообщении #313000 писал(а):

venco в сообщении #312907 писал(а):

Ну, по "моему" методу - 24.

Покажите, плз, "Ваш" метод.

Пробуем делить на 2. Потом на все нечётные числа, начиная с 3. На 24-ой итерации (47) находим делитель.

Gem в сообщении #313000 писал(а):

venco в сообщении #312907 писал(а):

А то ведь у меня есть ещё один метод: возьмём случайное число, например 47, попробуем разделить 9541 на 47. Делится! Итого - одна итерация.

Я полагал, что Вы понимаете разницу между случайным подбором числа и его вычислением.

Это я намекнул, что для метода Ферма выбранное вами число достаточно удобно, поэтому он нашёл делитель сравнительно быстро. Батороев предложил другое число, которое показывает насколько неэффективным может быть метод Ферма.

-- Вс апр 25, 2010 08:18:52 --

Gem в сообщении #313185 писал(а):

Батороев в сообщении #313132 писал(а):

Вам venco и я пытаемся лишь объяснить, что метод Ферма не очень эффективный.

Надо полагать, что с тех пор, как метод предложил Ферма, прошло немало времени.
В продолжении которого математики не сидели сложа руки.

Вы правы, с тех пор придумано много гораздо более эффективных методов. Даже для метода Ферма есть модификация, уменьшающая максимальное количество итераций до $\sqrt[3] n$.

Gem в сообщении #313185 писал(а):

Батороев в сообщении #313132 писал(а):

По-видимому, он занят и ответить не смог.

Скорее всего, принял меня за "упёртого" и решил не отвечать.

Ну это вы зря. Не всем же удаётся сидеть на форуме круглосуточно.

Gem в сообщении #313185 писал(а):

Вы полагаете, в этом случае будет меньше итераций?
Как найти все простые без итераций?
Или Вы предлагаете по справочнику?

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

[Батороев]

Gem в сообщении #313185 писал(а):

На досуге позабавляюсь.

Тогда и я, похоже, свободен.