Добро пожаловать в форум, Guest >> Войти | Регистрация | Поиск | Правила | | В избранное | Подписаться | ||
Все форумы / Программирование |
![]() ![]() |
Топик располагается на нескольких страницах: [1] 2 вперед Ctrl→ все |
Gennadiy Usov Member Откуда: Сообщений: 2275 |
Можно для чисел Мерсеннна Мn, где n – не является простым числом, найти сомножители для любого n. Правда, для больших чисел n могут быть найдены не все сомножители. А для очень больших чисел n найденных сомножителей будет немного. Это интересно? |
18 июн 19, 12:59 [21910551] Ответить | Цитировать Сообщить модератору |
mayton Member Откуда: loopback Сообщений: 50489 |
У чисел Мерсенна нет множителей по определению. |
18 июн 19, 15:28 [21910735] Ответить | Цитировать Сообщить модератору |
mayton Member Откуда: loopback Сообщений: 50489 |
Хотя вру. Есть. |
18 июн 19, 15:44 [21910754] Ответить | Цитировать Сообщить модератору |
Gennadiy Usov Member Откуда: Сообщений: 2275 |
Из вики: числа Мерсенна имеют вид Мn = 2^n-1. Среди этих чисел Mn есть простые числа, у которых n - есть простое число (не наоборот). |
18 июн 19, 19:07 [21910955] Ответить | Цитировать Сообщить модератору |
Barlone Member Откуда: Сообщений: 1448 |
2ab-1 делится на 2a-1 и на 2b-1 Вы знаете больше делителей? |
||
18 июн 19, 21:00 [21911015] Ответить | Цитировать Сообщить модератору |
x1ca4064 Member Откуда: Сообщений: 1224 |
Возможно, не понял, но 2(ab)(cd)-1 имеет больше делителей. |
||
18 июн 19, 23:40 [21911094] Ответить | Цитировать Сообщить модератору |
Gennadiy Usov Member Откуда: Сообщений: 2275 |
2^22 - 1 = 4194303 = 3 * 23 * 89 * 683 То есть, добавляется 683. С другой стороны, спасибо за формулу! Не обратил на неё внимание. Получается, 2ab-1 делится на 2a-1 и на 2b-1, а для частного находятся отдельно делители. Вопрос закрыт. |
||||
19 июн 19, 06:00 [21911139] Ответить | Цитировать Сообщить модератору |
Gennadiy Usov Member Откуда: Сообщений: 2275 |
Допустим, имеется число (Мерсенна) n = 85589933. Есть n1 = n/2 У меня вопрос: Сколько потребуется времени на компьютере (очень хорошем), чтобы посчитать величины от ? |
19 июн 19, 07:16 [21911154] Ответить | Цитировать Сообщить модератору |
kealon(Ruslan) Member Откуда: Нижневартовск Сообщений: 6228 |
Gennadiy Usov, довольно немного, даже на очень средненьком |
19 июн 19, 09:12 [21911210] Ответить | Цитировать Сообщить модератору |
mayton Member Откуда: loopback Сообщений: 50489 |
Первая часть формулы считается очень быстро до 2048 бит. Вангую что будут милисекунды. Потому - как это по сути заполнение единичным битом блок памяти. Вторая часть формулы где идет операция (mod n) - более тяжелая. Вангую - секунды и минуты до 2048 бит. Для n = 85589933 на наших компах задача скорее всего не решаемая. Возможно ее образцовое решение потребует вычислительный кластер из множества компов и какие-то методики распараллеливания этих операций. |
||
19 июн 19, 10:40 [21911287] Ответить | Цитировать Сообщить модератору |
kealon(Ruslan) Member Откуда: Нижневартовск Сообщений: 6228 |
mayton, прикалываешься? O(n) на весь массив, там одни cдвиги и вычитания v := 1; for i:= 1 to n1 do begin v := v shl 1; if v > n then v := v - n; Writeln(v - 1); end; |
19 июн 19, 11:14 [21911320] Ответить | Цитировать Сообщить модератору |
mayton Member Откуда: loopback Сообщений: 50489 |
Хм... вычитания. Звучит вкусно. |
19 июн 19, 13:26 [21911492] Ответить | Цитировать Сообщить модератору |
Gennadiy Usov Member Откуда: Сообщений: 2275 |
|
||
19 июн 19, 14:13 [21911554] Ответить | Цитировать Сообщить модератору |
kealon(Ruslan) Member Откуда: Нижневартовск Сообщений: 6228 |
фактически со скоростью записи на мой HDD диск почти пол гигабайта текстовой фигни |
||||
19 июн 19, 16:17 [21911672] Ответить | Цитировать Сообщить модератору |
Gennadiy Usov Member Откуда: Сообщений: 2275 |
|
||||
19 июн 19, 16:25 [21911683] Ответить | Цитировать Сообщить модератору |
Gennadiy Usov Member Откуда: Сообщений: 2275 |
|
||||
19 июн 19, 21:12 [21911866] Ответить | Цитировать Сообщить модератору |
kealon(Ruslan) Member Откуда: Нижневартовск Сообщений: 6228 |
|
||
20 июн 19, 00:14 [21911925] Ответить | Цитировать Сообщить модератору |
Gennadiy Usov Member Откуда: Сообщений: 2275 |
Просто выбираются простые числа из некоторого массива. Наверное, можно запомнить массив простых чисел от 1 до 90 000 000? |
||||
20 июн 19, 06:02 [21911959] Ответить | Цитировать Сообщить модератору |
kealon(Ruslan) Member Откуда: Нижневартовск Сообщений: 6228 |
Gennadiy Usov, т.е. хочешь проверить являются ли остатки простыми числами? какой смысл? |
20 июн 19, 08:42 [21911992] Ответить | Цитировать Сообщить модератору |
Gennadiy Usov Member Откуда: Сообщений: 2275 |
Ошибочная ветка. |
||
20 июн 19, 12:42 [21912149] Ответить | Цитировать Сообщить модератору |
Gennadiy Usov Member Откуда: Сообщений: 2275 |
Как известно, для чисел Мерсенна (вики): «Любой делитель составного числа Mр для простого p имеет вид 2*k*p +1, где k – натуральное число.» Спрашивается: почему нельзя для каждого Мр (начиная с р = 2) перебирать числа с целью поиска делителя (наименьшего)? При этом делитель не будет превышать числа, которое получается после деления. Тогда можно найти Мр, которые являются простыми числами. |
20 июн 19, 20:05 [21912482] Ответить | Цитировать Сообщить модератору |
kealon(Ruslan) Member Откуда: Нижневартовск Сообщений: 6228 |
вообще вроде формула была: n div 2 = 2*a*b + a + b |
||
21 июн 19, 09:47 [21912666] Ответить | Цитировать Сообщить модератору |
Gennadiy Usov Member Откуда: Сообщений: 2275 |
|
||||
21 июн 19, 10:24 [21912711] Ответить | Цитировать Сообщить модератору |
kealon(Ruslan) Member Откуда: Нижневартовск Сообщений: 6228 |
|
||
21 июн 19, 10:52 [21912737] Ответить | Цитировать Сообщить модератору |
Barlone Member Откуда: Сообщений: 1448 |
Придется перебирать значения k до 50 000 000 000 000 000. Перебирая по сто миллионов значений в секунду, лет за десять закончите. |
||
21 июн 19, 11:32 [21912782] Ответить | Цитировать Сообщить модератору |
Топик располагается на нескольких страницах: [1] 2 вперед Ctrl→ все |
Все форумы / Программирование | ![]() |