|
Ещё раз о тесте Ферма
|
|||
---|---|---|---|
#18+
kealon(Ruslan)Gennadiy Usov, тынц , может на какие мысли натолкнётДумал об этом. А как узнать: через какое число не проходит синусоида? Снова решето? А решето работает только с 1-ого числа. Его нельзя применить с К-ого числа. ... |
|||
:
Нравится:
Не нравится:
|
|||
13.06.2019, 09:05 |
|
Ещё раз о тесте Ферма
|
|||
---|---|---|---|
#18+
Gennadiy Usovkealon(Ruslan)Gennadiy Usov, тынц , может на какие мысли натолкнётДумал об этом. А как узнать: через какое число не проходит синусоида? Снова решето? А решето работает только с 1-ого числа. Его нельзя применить с К-ого числа. Без симуляции - никак. Можно предложить сверх-точные эксперименты в области например физики волн и ждать пока мы поймаем первую производную равную нулю как показано на картинке. Но это ожидание будет затягиваться пропорционально нашим хотелкам. Вопрос в том что мы хотим в цифрах. И сколько мы согласны ждать. ... |
|||
:
Нравится:
Не нравится:
|
|||
13.06.2019, 11:04 |
|
Ещё раз о тесте Ферма
|
|||
---|---|---|---|
#18+
Gennadiy UsovЕсть число (целое, нечётное). Как быстро определить: простое это число или нет? например так, если числа до 2000000000(тип long), с проверкой на чет/нечет, без списка простых чисел Код: vbnet 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16.
Код: vbnet 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 17. 18. 19. 20. 21. 22. 23. 24. 25. 26. 27. 28. 29. 30. 31. 32. 33. 34. 35. 36. 37. 38.
'выбор от 0 требуется чисел= 7 1 2 3 5 7 11 13 17 ' время в mсек= 12'выбор от 18 требуется чисел= 7 19 23 29 31 37 41 43 47' время в mсек= 0'выбор от 550 требуется чисел= 7 557 563 569 571 577 587 593 599' время в mсек= 0'выбор от 1000000 требуется чисел= 7 1000003 1000033 1000037 1000039 1000081 1000099 1000117 1000121' время в mсек= 12'выбор от 10000000 требуется чисел= 7 10000019 10000079 10000103 10000121 10000139 10000141 10000169 10000189' время в mсек= 0 ... |
|||
:
Нравится:
Не нравится:
|
|||
13.06.2019, 11:17 |
|
Ещё раз о тесте Ферма
|
|||
---|---|---|---|
#18+
Бабуля, твой код - ужасен ... |
|||
:
Нравится:
Не нравится:
|
|||
13.06.2019, 11:30 |
|
Ещё раз о тесте Ферма
|
|||
---|---|---|---|
#18+
maytonБабуля, твой код - ужасен спасибо за комплимент просто мне хотелось проанализировать время нахождения ПРОСТЫХ чисел в произвольном диапазоне не применяя списка простых чисел ----- а оформление --это вторично ... |
|||
:
Нравится:
Не нравится:
|
|||
13.06.2019, 11:48 |
|
Ещё раз о тесте Ферма
|
|||
---|---|---|---|
#18+
Мы уходим от первого сообщения топика. Там говорится о следующем: мне известно первое число 2047 (число Мерсенна), которое опровергает тест Ферма. Далее есть куча чисел Мерсенна, где тест Ферма не работает. А есть ли ещё простые числа, где этот тест не работает? ... |
|||
:
Нравится:
Не нравится:
|
|||
13.06.2019, 12:39 |
|
Ещё раз о тесте Ферма
|
|||
---|---|---|---|
#18+
Gennadiy UsovМы уходим от первого сообщения топика. Там говорится о следующем: мне известно первое число 2047 (число Мерсенна), которое опровергает тест Ферма. Далее есть куча чисел Мерсенна, где тест Ферма не работает. А есть ли ещё простые числа, где этот тест не работает?тест Ферма работает для всех простых чисел :-) читайте теорию, откуда и почему, а то за заголовок зацепились и пошли дальше сочинять ... |
|||
:
Нравится:
Не нравится:
|
|||
13.06.2019, 12:42 |
|
Ещё раз о тесте Ферма
|
|||
---|---|---|---|
#18+
kealon(Ruslan)Gennadiy UsovМы уходим от первого сообщения топика. Там говорится о следующем: мне известно первое число 2047 (число Мерсенна), которое опровергает тест Ферма. Далее есть куча чисел Мерсенна, где тест Ферма не работает. А есть ли ещё простые числа, где этот тест не работает?тест Ферма работает для всех простых чисел :-) читайте теорию, откуда и почему, а то за заголовок зацепились и пошли дальше сочинятьЧитайте сообщения внимательно. Число 2047 тест Ферма "распознаёт" как простое число. На самом деле, это число не является простым. Спрашивается: а есть ли ещё числа, которые тест Ферма считает простыми, а на самом деле эти числа не являются простыми (за исключением чисел Мерсенна)? ... |
|||
:
Нравится:
Не нравится:
|
|||
13.06.2019, 12:52 |
|
Ещё раз о тесте Ферма
|
|||
---|---|---|---|
#18+
Gennadiy UsovМы уходим от первого сообщения топика. Там говорится о следующем: мне известно первое число 2047 (число Мерсенна), которое опровергает тест Ферма. Далее есть куча чисел Мерсенна, где тест Ферма не работает. А есть ли ещё простые числа, где этот тест не работает? 2047 --не простое число в этом диапазоне пустые \требуется чисел= \ 2039 \ 2053 \ 2063 \ 2069 \ 2081 \ 2083 \ 2087 ... |
|||
:
Нравится:
Не нравится:
|
|||
13.06.2019, 12:53 |
|
Ещё раз о тесте Ферма
|
|||
---|---|---|---|
#18+
Gennadiy Usovkealon(Ruslan)пропущено... тест Ферма работает для всех простых чисел :-) читайте теорию, откуда и почему, а то за заголовок зацепились и пошли дальше сочинятьЧитайте сообщения внимательно. Число 2047 тест Ферма "распознаёт" как простое число. На самом деле, это число не является простым. Спрашивается: а есть ли ещё числа, которые тест Ферма считает простыми, а на самом деле эти числа не являются простыми (за исключением чисел Мерсенна)? Ну... должны-быть. Я-бы спорил на виски что есть. Можем заключить пари. По математической индукции - должны быть. С чего-бы ему быть одному этому числу? ... |
|||
:
Нравится:
Не нравится:
|
|||
13.06.2019, 12:56 |
|
Ещё раз о тесте Ферма
|
|||
---|---|---|---|
#18+
mayton, Вы меня удивляете насчет одного числа! Неужели не знаете, что тест Ферма определил для чисел Мерсенна Мр (р-степень) простые числа для тех чисел Мр, у которых р - простое число. А теперь посчитайте: сколько из чисел Мерсенна действительно являются простыми? ... |
|||
:
Нравится:
Не нравится:
|
|||
13.06.2019, 13:04 |
|
Ещё раз о тесте Ферма
|
|||
---|---|---|---|
#18+
Так что. Я проиграл бутылку Виски? ... |
|||
:
Нравится:
Не нравится:
|
|||
13.06.2019, 13:16 |
|
Ещё раз о тесте Ферма
|
|||
---|---|---|---|
#18+
Gennadiy Usov, довольно много(37-- помечены м) степень двойки минус 1меткаближайшее простое2-е простое31 31 37 63 м 67 71 127 127 131 255 м 257 263 511 (7*73) м 521 523 1023 м 1031 1033 2047 (23*89) м 2053 2063 4095 м 4099 4111 8191 8191 8209 16383 м 16411 16417 32767 м 32771 32779 65535 м 65537 65539 131071 131071 131101 262143 м 262147 262151 524287 524287 524309 1048575 м 1048583 1048589 2097151 м 2097169 2097211 4194303 м 4194319 4194329 8388607 м 8388617 8388619 16777215 м 16777259 16777289 33554431 м 33554467 33554473 67108863 м 67108879 67108913 134217727 м 134217757 134217773 268435455 м 268435459 268435463 536870911 м 536870923 536870951 1073741823 м 1073741827 1073741831 ... |
|||
:
Нравится:
Не нравится:
|
|||
13.06.2019, 13:18 |
|
Ещё раз о тесте Ферма
|
|||
---|---|---|---|
#18+
maytonТак что. Я проиграл бутылку Виски?Выиграли! Вы же спорили на то, что есть ещё такие числа. ... |
|||
:
Нравится:
Не нравится:
|
|||
13.06.2019, 13:20 |
|
Ещё раз о тесте Ферма
|
|||
---|---|---|---|
#18+
Нашел в вики число 341=11*31. Это число удовлетворяет тесту Ферма ... |
|||
:
Нравится:
Не нравится:
|
|||
13.06.2019, 15:18 |
|
Ещё раз о тесте Ферма
|
|||
---|---|---|---|
#18+
Есть предложение: нужно разделить все простые числа на подмножества, для каждого из которых будет существовать свой тест простоты, причём, достаточный. То есть, если число проходит один из таких тестов простоты, то оно является простым числом. На самом деле, будет несколько достаточных тестов простоты, которые применяются к конкретному числу в зависимости от признаков этого числа. ... |
|||
:
Нравится:
Не нравится:
|
|||
13.06.2019, 15:55 |
|
Ещё раз о тесте Ферма
|
|||
---|---|---|---|
#18+
на малых числах можно или online таблицы использовать, или online app-сервера расчётов у меня здесь https://rextester.com/live/QNKB4696 генерирует для всего диапазона/предела в 100 миллионов за <10 секунд (предел сервера настроенный для пользовательской сессии) а на домашнем за долю секунды, для 1млрд за от 2х до 20ти сек., на выделенном сервере будет ещё быстрее.. получилось количество праймов для предела в 1млрд = 50'847'534 т.е. 5% от верхней границы, по желанию если таблица в базе становится тяжелой то для ускорения (table scan) можно разнести по разным (где логика будет определять с какой таблицей проводить сравнение) здесь ещё ближайший можно проверить (в т.ч. и для 2^1024): https://www.wolframalpha.com/input/?i=PrimeQ(2038074743) https://www.wolframalpha.com/input/?i=PrimeQ(2^1024) https://www.wolframalpha.com/input/?i=prime(100000000) а по подписке у них и интеграция через API возможна. ... |
|||
:
Нравится:
Не нравится:
|
|||
13.06.2019, 16:56 |
|
Ещё раз о тесте Ферма
|
|||
---|---|---|---|
#18+
выше это в смысле ещё раз (надеюсь в последний) вклинюсь - вам шашечки или ехать? ... |
|||
:
Нравится:
Не нравится:
|
|||
13.06.2019, 16:57 |
|
Ещё раз о тесте Ферма
|
|||
---|---|---|---|
#18+
В сообщении 21908030 говорилось о разложении всех простых чисел на подмножества. За основу такого разложения можно взять тест Соловея – Штрассена. https://ru.wikipedia.org/wiki Если использовать в этом тесте привычную для нас степень 2, то получается следующие выражения: Имеется число n. Находим число m = (n – 1)/2 Тогда, если число простое, то . Далее тест предполагает рассмотреть другие степени, кроме 2, при этом число m является НОД между значением степени и n. Получается несколько раундов, и если во многих раундах тест покажет, что число простое, то с этой вероятность число n будет простым. Всё это создаёт массу вычислений, а также то, что есть вероятность того, что число n не является простым. Попробуем этот тест доработать. ... |
|||
:
Нравится:
Не нравится:
|
|||
14.06.2019, 06:17 |
|
Ещё раз о тесте Ферма
|
|||
---|---|---|---|
#18+
Рассматривается следующее изменение теста Соловея – Штрассена 21908306 : Для степени 2 получается следующие выражения: Имеется число n. Находим число m = (n + 1)/2 И определяем число Р . Число Р принимает следующие значения: а) Р = n -1 В этом случае число n определяем как простое число. Это и есть достаточный тест для определения числа n как простого числа б) Р = 1 В этом случае число n будет псевдопростым числом (тест Ферма данное число n определяет как простое число). в) Р не равно ни 1, ни (n - 1). В этом случае число n определяем как составное число. На диапазоне от 1 до 200 данный достаточный тест определяет 26 простых чисел и 18 псевдопростых чисел. И как следствие, с помощью этого достаточного теста можно точно определить простые числа на любом диапазоне, причем, очень быстро, с помощью одного вычисления по модулю. Псевдопростые числа будут рассмотрены позднее. ... |
|||
:
Нравится:
Не нравится:
|
|||
14.06.2019, 09:04 |
|
Ещё раз о тесте Ферма
|
|||
---|---|---|---|
#18+
Gennadiy Usov а) Р = n -1 В этом случае число n определяем как простое число. Это и есть достаточный тест для определения числа n как простого числа 3277, 29341, 49141, 80581, 88357, 104653, ... ... |
|||
:
Нравится:
Не нравится:
|
|||
14.06.2019, 09:43 |
|
Ещё раз о тесте Ферма
|
|||
---|---|---|---|
#18+
Числа составные, 2 (n-1)/2 == n-1 ... |
|||
:
Нравится:
Не нравится:
|
|||
14.06.2019, 09:46 |
|
Ещё раз о тесте Ферма
|
|||
---|---|---|---|
#18+
BarloneGennadiy Usov а) Р = n -1 В этом случае число n определяем как простое число. Это и есть достаточный тест для определения числа n как простого числа 3277, 29341, 49141, 80581, 88357, 104653, ...Спасибо за подсказку! Просто у меня нет программы на большие числа. Работаю в EXCEL, как все уже знают. Буду рассматривать эту ветку. Я её уже видел, но думал, что проскочит. Не получилось. ... |
|||
:
Нравится:
Не нравится:
|
|||
14.06.2019, 10:45 |
|
|
start [/forum/topic.php?fid=16&msg=39825928&tid=1339906]: |
0ms |
get settings: |
10ms |
get forum list: |
16ms |
check forum access: |
4ms |
check topic access: |
4ms |
track hit: |
174ms |
get topic data: |
11ms |
get forum data: |
3ms |
get page messages: |
69ms |
get tp. blocked users: |
2ms |
others: | 235ms |
total: | 528ms |
0 / 0 |