| Вопрос: Числа Мерсенна - Алгоритм проверки ? | Добавлено: 25.07.06 22:33 |
Автор вопроса:  VisBas | Web-сайт: chipmicro.narod.ru
|
|
Как проверить является ли число 2^n-1 простым, используя тест Люка-Лемера ?
Непонятен сам тест, кто его понимает, обьясните пожалуйста. |
| Ответы | Всего ответов: 6 |
|
Номер ответа: 1 Автор ответа:  Серёга ICQ: 262809473 Вопросов: 17 Ответов: 561 |
Web-сайт: Профиль | | #1 | Добавлено: 26.07.06 03:03 |
|
http://ruwiki.com/article/%D0%A2%D0%B5%D1%81%D1%82_%D0%9B%D1%8E%D0%BA%D0%B0_%E2%80%94_%D0%9B%D0%B5%D0%BC%D0%B5%D1%80%D0%B0
И если я ничего не напутал, то примерно так: Private Function Luck_Meller_Test(p As Long, Errorka As String) As Boolean
If p < 3 Then Errorka = "tipa ERROR  ))"
Exit Function End If Dim L() As Long, M_p As Long, i As Long M_p = (2 ^ p) - 1 ReDim L(1 To p - 1) As Long L(1) = 4 For i = 2 To p - 1 L(i) = (L(i - 1) ^ 2) - 2 Next i If (L(p - 1) Mod M_p) = 0 Then Luck_Meller_Test = True End Function Private Sub Command1_Click() Dim Errorka As String If Luck_Meller_Test(Val(Text1.Text), Errorka) And Errorka = "" Then MsgBox "prostoe" ElseIf Errorka = "" Then MsgBox "sostavnoe" Else MsgBox Errorka End If End Sub Но, мат. движок VB6 позволяет проверить числа только до 6 (включительно). Далее OVERFLOW. Так что для более крутых вычислений прийдется написать свой движок. |
||
|
Номер ответа: 2 Автор ответа: Sharp Лидер форума ICQ: 216865379 Вопросов: 106 Ответов: 9979 |
Web-сайт: Профиль | | #2 | Добавлено: 26.07.06 03:13 |
|
А в чем проблема? В доказательстве?
http://ru.wikipedia.org/wiki/%D0%A2%D0%B5%D1%81%D1%82_%D0%9B%D1%8E%D0%BA%D0%B0-%D0%9B%D0%B5%D0%BC%D0%B5%D1%80%D0%B0 Очевидно, почему p должно быть простым, иначе 2^p-1 делится на 2^k-1, где k - любой делитель p, больший 1. А вот формула для чисел Люка на Википедии дана неверно, правильная вместе со ссылкой на работу по этой теме в справочнике Слоана: http://www.research.att.com/~njas/sequences/A018844 |
||
|
Номер ответа: 3 Автор ответа: VisBasВопросов: 44 Ответов: 127 |
Web-сайт: Профиль | | #3 | Добавлено: 26.07.06 19:27 |
|
И если я ничего не напутал, то примерно так:
Private Function Luck_Meller_Test(p As Long, Errorka As String) As Boolean If p < 3 Then Errorka = "tipa ERROR ))"
Exit Function End If Dim L() As Long, M_p As Long, i As Long M_p = (2 ^ p) - 1 ReDim L(1 To p - 1) As Long L(1) = 4 For i = 2 To p - 1 L(i) = (L(i - 1) ^ 2) - 2 Next i If (L(p - 1) Mod M_p) = 0 Then Luck_Meller_Test = True End Function Private Sub Command1_Click() Dim Errorka As String If Luck_Meller_Test(Val(Text1.Text), Errorka) And Errorka = "" Then MsgBox "prostoe" ElseIf Errorka = "" Then MsgBox "sostavnoe" Else MsgBox Errorka End If End Sub Ой наутал.. Совсем не так ! Спасибо за помощь, но вопрос остается открытым. |
||
|
Номер ответа: 4 Автор ответа: VisBasВопросов: 44 Ответов: 127 |
Web-сайт: Профиль | | #4 | Добавлено: 27.07.06 19:48 |
| Спасибо за помощь, сам разобрался. | ||
|
Номер ответа: 5 Автор ответа: СерёгаICQ: 262809473 Вопросов: 17 Ответов: 561 |
Web-сайт: Профиль | | #5 | Добавлено: 27.07.06 20:06 |
| Поделишься? | ||
|
Номер ответа: 6 Автор ответа: VisBasВопросов: 44 Ответов: 127 |
Web-сайт: Профиль | | #6 | Добавлено: 27.07.06 21:02 |
| Пришли е-маил, скину исходник. vb53@yandex.ru | ||
Страница: 1 |