Смотрел различные алгоритмы нахождения простых чисел от 1го до N:

Простое число это число имеющее только 2 различных делителя. Соответственно когда мы рассматриваем числа от 1го до N-1 и если число N в этом промежутке ни на что не поделилось оно простое из определения.

Также существует алгоритм по которому мы рассматриваем числа от 1го до корня из N. У меня возникает вопрос: почему он работает? То есть по какому праву мы рассматриваем числа только до корня? На практике этот метод не дает сбоев, вычисления также дают верный результат. Но получить формулу, доказывающую это мне не удается.

Прошу растолковать данный метод

задан 26 Дек '11 1:02

изменен 26 Дек '11 1:05

10|600 символов нужно символов осталось
2

Дело в том, что если число a делится на число b, то, очевидно $%c=a/b$% также целое и $%a=b\cdot c$%. Но оба числа не могут быть больше $%\sqrt{a}$%, поэтому, одно из них не больше корня и мы его найдем.

ссылка

отвечен 26 Дек '11 1:11

10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

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

Присоединяйтесь!

отмечен:

×571
×133

задан
26 Дек '11 1:02

показан
948 раз

обновлен
26 Дек '11 1:11

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru