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

[Cash]

iifat, все верно. Только это не проверка на простоту, а разложение на множители - метод Ферма. Соответственно для задачи проверки на простоту - ну и микроскопом гвозди тоже можно забивать.

[serega57]

Cash в сообщении #828375 писал(а):

iifat, все верно. Только это не проверка на простоту, а разложение на множители - метод Ферма. Соответственно для задачи проверки на простоту - ну и микроскопом гвозди тоже можно забивать.

Всё верно речи об этом не шло установлен критерий ограничения. Ответа так правильного почему то некто не дал. А когда выяснили так как всегда всем известно что тогда спорили. Поиск квадрата такого вида начинается с $x=\left\lceil {\sqrt {n}}\right\rceil$ — наименьшего числа, это с википедии.Я не говорил что таким способом Вы путаете у меня не о каких вычитаний с квадратами. Только 1 раз после чего сплошной перебор не превосходяший данного ограничения. А у Ферма в зависимости от числа в плоть до самого квадратного корня если число простое.

[serega57]

Cash в сообщении #828375 писал(а):

микроскопом гвозди тоже можно забивать.

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

[provincialka]

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

[serega57]

provincialka в сообщении #828689 писал(а):

Не новый критерий, а другой метод. Если проверять простые делители - то до квадратного корня.

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

[iifat]

provincialka в сообщении #828689 писал(а):

Не новый критерий, а другой метод

Метод-то другой, но, как неоднократно показали, минимальный делитель $N$ лежит в интервале $[2;\sqrt N]$ и сузить его не выйдет.

[serega57]

iifat в сообщении #828748 писал(а):

provincialka в сообщении #828689 писал(а):

Не новый критерий, а другой метод

Метод-то другой, но, как неоднократно показали, минимальный делитель $N$ лежит в интервале $[2;\sqrt N]$ и сузить его не выйдет.

Руст смог сам доказать в моей задачи что если квадратный корен из числа дробная часть меньше 0,5 то не один делитель не может быть больше...

-- Чт фев 20, 2014 13:08:55 --

serega57 в сообщении #825570 писал(а):

Докажите что если $ N=\alpha^{2} +n . ~\alpha>n,~ N$ нечетное. То ни одно такое N не может иметь таких простых делителей p которые $ \alpha-\sqrt{\alpha } +2<P<\alpha$

Руст в сообщении #825736 писал(а):

Пусть р простое. Тогда $\alpha=p+k$, где $1\le k<\sqrt \alpha -2$.
Делитель $\frac{N}{p}=p+2k+2m$ (из-за нечетности).
Проверяем m=0. $p(p+2k)=\alpha^2-k^2<N$.
Проверяем $m=1$.
$p(p+2k+2)=\alpha^2-k^2+2p=\alpha^2+2\alpha-2k-k^2=\alpha^2+2\alpha+1-(k+1)^2\ge \alpha^2+\alpha$,
если $(k+1)^2\le \alpha +1$, т.е если $k\le \sqrt{\alpha+1}-1$.
Т.е. ваш результат даже несколько усилился.

serega57 в сообщении #825820 писал(а):

Теперь попробуйте дать определение для всех N, $ N= \alpha^2-n$// $\alpha>n$ Для которых не будет простых делителей $\alpha- \sqrt{ \alpha }<p<\alpha$/

Э то выяснили с товарищами вчера.

[B@R5uk]

Пусть $N=a^2$. Сколько надо прибавить к $N$, чтобы получить следующий точный квадрат? Ответ, на мой взгляд: надо прибавить $n=2a+1$. Получается, теорема, приведённая топикстартером, справедлива для весьма узкого числа чисел (а точнее, для половины нечётных).

-- 20.02.2014, 16:30 --

provincialka в сообщении #828352 писал(а):

Извлекать корень из сверхбольшого числа - тоже не сахар.

Извлечение корня, как раз, очень простая операция. Она делается на порядки проще, чем деление.

-- 20.02.2014, 16:33 --

serega57 в сообщении #828330 писал(а):

НЕТ САСТОВНОЕ

[serega57]

B@R5uk в сообщении #828839 писал(а):

Пусть $N=a^2$. Сколько надо прибавить к $N$, чтобы получить следующий точный квадрат? Ответ, на мой взгляд: надо прибавить $n=2a+1$. Получается, теорема, приведённая топикстартером, справедлива для весьма узкого числа чисел (а точнее, для половины нечётных).

А для второй половины

B@R5uk в сообщении #828839 писал(а):

Для которых не будет простых делителей $\alpha- \sqrt{ \alpha }<p<\alpha$

даже доказывать не надо ибо все делители которые будут больше указанного значения будут как разница квадратов. Именно для этого мы и проверяем на это если это так число сразу знаем составное. И от метода Ферма когда для этого долго здесь сразу.Если нет квадрата разницы то критерий

B@R5uk в сообщении #828839 писал(а):

Для которых не будет простых делителей $\alpha- \sqrt{ \alpha }<p<\alpha$

Установлен. И не новый способ а новый критерий.

[provincialka]

serega57, вам чего надо? Ну, предложили вы некий способ. Путем героических многодневных усилий форума мы, вроде, разобрались, что вы имели в виду. Вот и славно! Теперь отдыхайте и смотрите олимпиаду.

[serega57]

provincialka в сообщении #829027 писал(а):

serega57, вам чего надо? Ну, предложили вы некий способ. Путем героических многодневных усилий форума мы, вроде, разобрались, что вы имели в виду. Вот и славно! Теперь отдыхайте и смотрите олимпиаду.

Не поверите мне ничего не надо. Вам был задан вопрос на который не ответили.А что я имел в виду это должны были сделать сами. Да и после наших хоккеистов и смотреть не хочется.

[provincialka]

serega57 в сообщении #829084 писал(а):

Вам был задан вопрос на который не ответили

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

[B@R5uk]

serega57 в сообщении #828891 писал(а):

ибо все делители которые будут больше указанного значения будут как разница квадратов...

Если честно, вообще не понял, что эта фраза значит.

Для чисел, у которых остаток от извлечения целочисленного корня больше самого корня (то есть для случая $\alpha<n<2\alpha$ в выражении $N=\alpha^2+n$), методом грубой силы я нашёл приличное число контрпримеров к утверждению в первом посте:

$35=5\cdot7=5^2+10 \\ 143=11\cdot13=11^2+22 \\ 221=13\cdot17=14^2+25 \\ 323=17\cdot19=17^2+34 \\ 391=17\cdot23=19^2+30 \\ 437=19\cdot23=20^2+37 \\ 667=23\cdot29=25^2+42 \\ 713=23\cdot31=26^2+37 \\ 899=29\cdot31=29^2+58 \\ 1073=29\cdot37=32^2+49 \\ 1147=31\cdot37=33^2+58 \\ 1517=37\cdot41=38^2+73 \\ 1591=37\cdot43=39^2+70 \\ 1739=37\cdot47=41^2+58 \\ 1763=41\cdot43=41^2+82 \\ 1927=41\cdot47=43^2+78 \\ 2021=43\cdot47=44^2+85 \\ 2279=43\cdot53=47^2+70 \\ 2491=47\cdot53=49^2+90 \\ 2773=47\cdot59=52^2+69$

[provincialka]

B@R5uk, не начинайте все заново. Вы просто не так поняли, что говорит ТС. Что и немудрено при его способе выражаться.
Имеется в виду следующее. Рассмотрим число $n$. Корень из него округленно равен $k$. Если округление идет вверх, рассмотрим число $p=k^2-n$. В случае, когда $p=m^2$, исходное число - составное. Если же не квадрат, то для проверки простоты $n$ достаточно попытаться поделить его на простые, не большие $k-\sqrt k$, потому что более "крупных" простых делителей у него нет.
Там еще что-то было про нечетность...

[serega57]

provincialka в сообщении #829086 писал(а):

serega57 в сообщении #829084 писал(а):

Вам был задан вопрос на который не ответили

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

Вы меня простите выше сказанное не относилось к Вам . Я Вам говорил большое спасибо и не коем образом хотел за Вашу помощь что то иметь лично против Вас.

B@R5uk в сообщении #829100 писал(а):

serega57 в сообщении #828891 писал(а):

ибо все делители которые будут больше указанного значения будут как разница квадратов...

Если честно, вообще не понял, что эта фраза значит.

Для чисел, у которых остаток от извлечения целочисленного корня больше самого корня (то есть для случая $\alpha<n<2\alpha$ в выражении $N=\alpha^2+n$), методом грубой силы я нашёл приличное число контрпримеров к утверждению в первом посте:
Здесь нет не одного контрпримера, все эти числа лежат за приделами для данных квадратов и принадлежат уже к другому квадрату.Мои интервалы только для чисел принадлежащих к одному квадратному корню.
$35=5\cdot7=5^2+10 \\ 143=11\cdot13=11^2+22 \\ 667=23\cdot29=25^2+42 \\ 713=23\cdot31=26^2+37 \\ и т д 899=29\cdot31=29^2+58 \\ 1073=29\cdot37=32^2+49 \\ 1147=31\cdot37=33^2+58 \\ 1517=37\cdot41=38^2+73 \\ 1591=37\cdot43=39^2+70 \\ 1739=37\cdot47=41^2+58 \\ 1763=41\cdot43=41^2+82 \\ 1927=41\cdot47=43^2+78 \\ 2021=43\cdot47=44^2+85 \\ 2279=43\cdot53=47^2+70 \\ 2491=47\cdot53=49^2+90 \\ 2773=47\cdot59=52^2+69$

221=13\cdot17=14^2+25 \\ $15\cdot15-4$
323=17\cdot19=17^2+34 \\ $ 18\cdot18-1$
391=17\cdot23=19^2+30 \\ $ 20\cdot20-9$
437=19\cdot23=20^2+37 \\ $ 21\cdot21-4$
Все ваши корни надо увеличить на 1 и от этих значений отнимать число