ReSQL.ru
     
powered by simpleCommunicator - 2.0.50     © 2025 Programmizd 02
Мобильная версия    Контакт    Правила    FAQ    Помощь
Доб. в избранное | Игнор. тему | Прикреп. тему | Пометить прочит. / непрочит. | Фильтр
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Ещё раз о тесте Ферма
25 сообщений из 283, страница 2 из 12
  2  все
Ещё раз о тесте Ферма
    #39825928
kealon(Ruslan)
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
kealon(Ruslan)
Участник
Gennadiy Usov,

тынц , может на какие мысли натолкнёт
...
Рейтинг: 0 / 0
13.06.2019, 07:48
| Ответить | Цитировать | Написать  
Ещё раз о тесте Ферма
    #39825963
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Gennadiy Usov
Гость
kealon(Ruslan)Gennadiy Usov,
тынц , может на какие мысли натолкнётДумал об этом.

А как узнать: через какое число не проходит синусоида?
Снова решето?
А решето работает только с 1-ого числа. Его нельзя применить с К-ого числа.
...
Рейтинг: 0 / 0
13.06.2019, 09:05
| Ответить | Цитировать | Написать  
Ещё раз о тесте Ферма
    #39826022
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Gennadiy Usovkealon(Ruslan)Gennadiy Usov,
тынц , может на какие мысли натолкнётДумал об этом.

А как узнать: через какое число не проходит синусоида?
Снова решето?
А решето работает только с 1-ого числа. Его нельзя применить с К-ого числа.
Без симуляции - никак. Можно предложить сверх-точные эксперименты в области например
физики волн и ждать пока мы поймаем первую производную равную нулю как показано
на картинке. Но это ожидание будет затягиваться пропорционально нашим хотелкам.

Вопрос в том что мы хотим в цифрах. И сколько мы согласны ждать.
...
Рейтинг: 0 / 0
13.06.2019, 11:04
| Ответить | Цитировать | Написать  
Ещё раз о тесте Ферма
    #39826025
Фотография ПЕНСИОНЕРКА
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
ПЕНСИОНЕРКА
Участник
Gennadiy UsovЕсть число (целое, нечётное).
Как быстро определить: простое это число или нет?
например так, если числа до 2000000000(тип long), с проверкой на чет/нечет, без списка простых чисел
Код: vbnet
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
Option Explicit
Sub mm()
Dim a As Long
Debug.Print "выбор  простых в интервале=============="
''''''''''''''''''''''''''''''
mm190613a 0, 7
mm190613a 18, 7
mm190613a 550, 7
''''''''''''''''''''''''''''''
a = 10 ^ 6
mm190613a a, 7
''''''''''''''''''''''''''''''
a = 10 ^ 7
mm190613a a, 7

End Sub


Код: 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.
Sub mm190613a(n1z As Long, n2z As Long)
Dim n0 As Long, j1 As Long, jm As Long, jp As Long, zkol As Long, dt
Dim j2 As Long, j2k As Long

dt = Timer
Debug.Print "выбор от "; n1z; " \требуется чисел= "; n2z;

''Debug.Print 1; 2; 3; 5;
If (n1z Mod 2) = 0 Then
n0 = n1z + 1
Else
n0 = n1z
End If
If n0 < 7 Then
Debug.Print "\1 \2 \3 \5 ";
n0 = 7
End If

    For j1 = n0 To 1000000000 Step 2
    j2k = Sqr(j1)
        For j2 = 3 To j2k Step 2
        If (j1 Mod j2) = 0 Then GoTo nj1
        Next j2
    
    jm = j1 - 1
    jp = j1 + 1
        If (jm Mod 6) = 0 Or (jp Mod 6) = 0 Then
        Debug.Print "\"; j1;
        zkol = zkol + 1
        If zkol > n2z Then Exit For
        End If
    
nj1:
    Next j1
    Debug.Print
 Debug.Print " время в mсек\="; (Timer - dt) * 1000 \ 1

End Sub


'выбор от 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
...
Рейтинг: 0 / 0
13.06.2019, 11:17
| Ответить | Цитировать | Написать  
Ещё раз о тесте Ферма
    #39826034
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Бабуля, твой код - ужасен
...
Рейтинг: 0 / 0
13.06.2019, 11:30
| Ответить | Цитировать | Написать  
Ещё раз о тесте Ферма
    #39826046
Фотография ПЕНСИОНЕРКА
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
ПЕНСИОНЕРКА
Участник
maytonБабуля, твой код - ужасен

спасибо за комплимент
просто мне хотелось проанализировать время нахождения ПРОСТЫХ чисел в произвольном диапазоне не применяя списка простых чисел
-----
а оформление --это вторично
...
Рейтинг: 0 / 0
13.06.2019, 11:48
| Ответить | Цитировать | Написать  
Ещё раз о тесте Ферма
    #39826078
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Gennadiy Usov
Гость
Мы уходим от первого сообщения топика.

Там говорится о следующем:
мне известно первое число 2047 (число Мерсенна), которое опровергает тест Ферма.
Далее есть куча чисел Мерсенна, где тест Ферма не работает.

А есть ли ещё простые числа, где этот тест не работает?
...
Рейтинг: 0 / 0
13.06.2019, 12:39
| Ответить | Цитировать | Написать  
Ещё раз о тесте Ферма
    #39826086
kealon(Ruslan)
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
kealon(Ruslan)
Участник
Gennadiy UsovМы уходим от первого сообщения топика.

Там говорится о следующем:
мне известно первое число 2047 (число Мерсенна), которое опровергает тест Ферма.
Далее есть куча чисел Мерсенна, где тест Ферма не работает.

А есть ли ещё простые числа, где этот тест не работает?тест Ферма работает для всех простых чисел :-)

читайте теорию, откуда и почему, а то за заголовок зацепились и пошли дальше сочинять
...
Рейтинг: 0 / 0
13.06.2019, 12:42
| Ответить | Цитировать | Написать  
Ещё раз о тесте Ферма
    #39826100
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Gennadiy Usov
Гость
kealon(Ruslan)Gennadiy UsovМы уходим от первого сообщения топика.
Там говорится о следующем:
мне известно первое число 2047 (число Мерсенна), которое опровергает тест Ферма.
Далее есть куча чисел Мерсенна, где тест Ферма не работает.
А есть ли ещё простые числа, где этот тест не работает?тест Ферма работает для всех простых чисел :-)
читайте теорию, откуда и почему, а то за заголовок зацепились и пошли дальше сочинятьЧитайте сообщения внимательно.

Число 2047 тест Ферма "распознаёт" как простое число.
На самом деле, это число не является простым.

Спрашивается:
а есть ли ещё числа, которые тест Ферма считает простыми, а на самом деле эти числа не являются простыми (за исключением чисел Мерсенна)?
...
Рейтинг: 0 / 0
13.06.2019, 12:52
| Ответить | Цитировать | Написать  
Ещё раз о тесте Ферма
    #39826102
Фотография ПЕНСИОНЕРКА
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
ПЕНСИОНЕРКА
Участник
Gennadiy UsovМы уходим от первого сообщения топика.

Там говорится о следующем:
мне известно первое число 2047 (число Мерсенна), которое опровергает тест Ферма.
Далее есть куча чисел Мерсенна, где тест Ферма не работает.

А есть ли ещё простые числа, где этот тест не работает?
2047 --не простое число

в этом диапазоне пустые
\требуется чисел= \ 2039 \ 2053 \ 2063 \ 2069 \ 2081 \ 2083 \ 2087
...
Рейтинг: 0 / 0
13.06.2019, 12:53
| Ответить | Цитировать | Написать  
Ещё раз о тесте Ферма
    #39826108
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Gennadiy Usovkealon(Ruslan)пропущено...
тест Ферма работает для всех простых чисел :-)
читайте теорию, откуда и почему, а то за заголовок зацепились и пошли дальше сочинятьЧитайте сообщения внимательно.

Число 2047 тест Ферма "распознаёт" как простое число.
На самом деле, это число не является простым.

Спрашивается:
а есть ли ещё числа, которые тест Ферма считает простыми, а на самом деле эти числа не являются простыми (за исключением чисел Мерсенна)?
Ну... должны-быть. Я-бы спорил на виски что есть. Можем заключить пари.
По математической индукции - должны быть. С чего-бы ему быть одному этому числу?
...
Рейтинг: 0 / 0
13.06.2019, 12:56
| Ответить | Цитировать | Написать  
Ещё раз о тесте Ферма
    #39826117
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Gennadiy Usov
Гость
mayton,
Вы меня удивляете насчет одного числа!

Неужели не знаете, что тест Ферма определил для чисел Мерсенна Мр (р-степень) простые числа для тех чисел Мр, у которых р - простое число.
А теперь посчитайте: сколько из чисел Мерсенна действительно являются простыми?
...
Рейтинг: 0 / 0
13.06.2019, 13:04
| Ответить | Цитировать | Написать  
Ещё раз о тесте Ферма
    #39826128
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Так что. Я проиграл бутылку Виски?
...
Рейтинг: 0 / 0
13.06.2019, 13:16
| Ответить | Цитировать | Написать  
Ещё раз о тесте Ферма
    #39826131
Фотография ПЕНСИОНЕРКА
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
ПЕНСИОНЕРКА
Участник
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
...
Рейтинг: 0 / 0
13.06.2019, 13:18
| Ответить | Цитировать | Написать  
Ещё раз о тесте Ферма
    #39826133
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Gennadiy Usov
Гость
maytonТак что. Я проиграл бутылку Виски?Выиграли!

Вы же спорили на то, что есть ещё такие числа.
...
Рейтинг: 0 / 0
13.06.2019, 13:20
| Ответить | Цитировать | Написать  
Ещё раз о тесте Ферма
    #39826188
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Gennadiy Usov
Гость
Нашел в вики число 341=11*31.

Это число удовлетворяет тесту Ферма
...
Рейтинг: 0 / 0
13.06.2019, 15:18
| Ответить | Цитировать | Написать  
Ещё раз о тесте Ферма
    #39826213
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Gennadiy Usov
Гость
Есть предложение:
нужно разделить все простые числа на подмножества, для каждого из которых будет существовать свой тест простоты, причём, достаточный.
То есть, если число проходит один из таких тестов простоты, то оно является простым числом.

На самом деле, будет несколько достаточных тестов простоты,
которые применяются к конкретному числу в зависимости от признаков этого числа.
...
Рейтинг: 0 / 0
13.06.2019, 15:55
| Ответить | Цитировать | Написать  
Ещё раз о тесте Ферма
    #39826260
Фотография vikkiv
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
vikkiv
Участник
на малых числах можно или 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 возможна.
...
Рейтинг: 0 / 0
13.06.2019, 16:56
| Ответить | Цитировать | Написать  
Ещё раз о тесте Ферма
    #39826261
Фотография vikkiv
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
vikkiv
Участник
выше это в смысле ещё раз (надеюсь в последний) вклинюсь - вам шашечки или ехать?
...
Рейтинг: 0 / 0
13.06.2019, 16:57
| Ответить | Цитировать | Написать  
Ещё раз о тесте Ферма
    #39826379
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Gennadiy Usov
Гость
В сообщении 21908030 говорилось о разложении всех простых чисел на подмножества.

За основу такого разложения можно взять тест Соловея – Штрассена.
https://ru.wikipedia.org/wiki

Если использовать в этом тесте привычную для нас степень 2, то получается следующие выражения:

Имеется число n.
Находим число m = (n – 1)/2
Тогда, если число простое, то
.

Далее тест предполагает рассмотреть другие степени, кроме 2, при этом число m является НОД между значением степени и n.

Получается несколько раундов, и если во многих раундах тест покажет, что число простое, то с этой вероятность число n будет простым.

Всё это создаёт массу вычислений, а также то, что есть вероятность того, что число n не является простым.
Попробуем этот тест доработать.
...
Рейтинг: 0 / 0
14.06.2019, 06:17
| Ответить | Цитировать | Написать  
Ещё раз о тесте Ферма
    #39826407
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Gennadiy Usov
Гость
Рассматривается следующее изменение теста Соловея – Штрассена 21908306 :

Для степени 2 получается следующие выражения:

Имеется число n.
Находим число m = (n + 1)/2
И определяем число Р
.

Число Р принимает следующие значения:

а) Р = n -1
В этом случае число n определяем как простое число.
Это и есть достаточный тест для определения числа n как простого числа
б) Р = 1
В этом случае число n будет псевдопростым числом (тест Ферма данное число n определяет как простое число).

в) Р не равно ни 1, ни (n - 1).
В этом случае число n определяем как составное число.

На диапазоне от 1 до 200 данный достаточный тест определяет 26 простых чисел и 18 псевдопростых чисел.

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

Псевдопростые числа будут рассмотрены позднее.
...
Рейтинг: 0 / 0
14.06.2019, 09:04
| Ответить | Цитировать | Написать  
Ещё раз о тесте Ферма
    #39826424
Barlone
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Barlone
Участник
Gennadiy Usov а) Р = n -1
В этом случае число n определяем как простое число.
Это и есть достаточный тест для определения числа n как простого числа

3277, 29341, 49141, 80581, 88357, 104653, ...
...
Рейтинг: 0 / 0
14.06.2019, 09:43
| Ответить | Цитировать | Написать  
Ещё раз о тесте Ферма
    #39826425
Barlone
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Barlone
Участник
Числа составные, 2 (n-1)/2 == n-1
...
Рейтинг: 0 / 0
14.06.2019, 09:46
| Ответить | Цитировать | Написать  
Ещё раз о тесте Ферма
    #39826461
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Gennadiy Usov
Гость
BarloneGennadiy Usov а) Р = n -1
В этом случае число n определяем как простое число.
Это и есть достаточный тест для определения числа n как простого числа
3277, 29341, 49141, 80581, 88357, 104653, ...Спасибо за подсказку!

Просто у меня нет программы на большие числа.
Работаю в EXCEL, как все уже знают.

Буду рассматривать эту ветку.

Я её уже видел, но думал, что проскочит.
Не получилось.
...
Рейтинг: 0 / 0
14.06.2019, 10:45
| Ответить | Цитировать | Написать  
Ещё раз о тесте Ферма
    #39826462
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Вспоминается анекдот. ".... Женится тебе пора, барин".
...
Рейтинг: 0 / 0
14.06.2019, 10:46
| Ответить | Цитировать | Написать  
25 сообщений из 283, страница 2 из 12
  2  все
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Ещё раз о тесте Ферма
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
Польз. соглашение
NoSQL.ru       Новости, Чат       Фотоальбом: Участники, Встречи
Закрыть
start [/forum/topic.php?fid=16&msg=39826034&tid=1339906]:
 0ms
get settings:
 10ms
get forum list:
 12ms
check forum access:
 4ms
check topic access:
 4ms
track hit:
 56ms
get topic data:
 11ms
get forum data:
 5ms
get page messages:
 61ms
get tp. blocked users:
 1ms
others: 18ms
total:  182ms
созд. / загр.: 182ms
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]