Добро пожаловать в форум, Guest >> Войти | Регистрация | Поиск | Правила | | В избранное | Подписаться | ||
Все форумы / Программирование |
![]() ![]() |
Топик располагается на нескольких страницах: ←Ctrl назад 1 2 3 4 5 6 [7] 8 9 10 вперед Ctrl→ все |
Barlone Member Откуда: Сообщений: 1451 |
А насчет практики - есть такое число Скьюза. Это про гипотезу, что количество простых чисел, не превосходящих n, меньше чем интегральный логарифм li(n). Она выполняется до 10316, а потом перестает выполняться... Вы свой алгоритм хотя бы до 10316 проверяли? |
3 окт 19, 13:08 [21985803] Ответить | Цитировать Сообщить модератору |
Basil A. Sidorov Member Откуда: Сообщений: 10908 |
Вот я в детстве иногда лепил из пластилина. Кое-что из моих "творений" даже стояло дома на видном месте. И что? Кому и зачем всё это может быть интересно? P.S. "Всё" - не столько мои излияния, сколько ваши "труды". Уж не обижайтесь. |
||
3 окт 19, 13:10 [21985806] Ответить | Цитировать Сообщить модератору |
Gennadiy Usov Member Откуда: Сообщений: 2357 |
что среди представленных чисел (одно число в перечне) 0 простых чисел. (слово "нет" - лишнее, убираю) 2019-10-03-13.09.54 -число- 3825123056546413053 -простых чисел- 0 2019-10-03-13.09.54 |
||||
3 окт 19, 13:11 [21985809] Ответить | Цитировать Сообщить модератору |
Barlone Member Откуда: Сообщений: 1451 |
Хотя, вы в степень то наверное встроенной функцией возводили? |
||||
3 окт 19, 13:11 [21985810] Ответить | Цитировать Сообщить модератору |
Barlone Member Откуда: Сообщений: 1451 |
|
||||
3 окт 19, 13:15 [21985812] Ответить | Цитировать Сообщить модератору |
Basil A. Sidorov Member Откуда: Сообщений: 10908 |
А выдать что-то вроде: Всего чисел - xxx? Ну или учитывая, что простые числа, типа, "редкие", по мере проверки просто печать список "эвристически простых", а по итогу выдать общую статистику? |
||
3 окт 19, 13:16 [21985814] Ответить | Цитировать Сообщить модератору |
Barlone Member Откуда: Сообщений: 1451 |
|
||||
3 окт 19, 13:16 [21985815] Ответить | Цитировать Сообщить модератору |
Gennadiy Usov Member Откуда: Сообщений: 2357 |
У меня цикл по нечётным числам с шагом 2 на диапазоне, я назначил число и ограничил на +1, а цикл (на то он и цикл) прибавляет и сравнивает с ограничителем. А печать идёт после выхода из цикла. Внутри цикла составные числа программе не нужны, поэтому эти числа там не печатаются. Исправил (отнял 2): 2019-10-03-13.19.53 -число- 3825123056546413051 -простых чисел- 0 2019-10-03-13.19.53 |
||||
3 окт 19, 13:26 [21985834] Ответить | Цитировать Сообщить модератору |
Gennadiy Usov Member Откуда: Сообщений: 2357 |
На диапазоне 2^1024 количество простых чисел на диапазоне совпало с расчётом mayton. А вопрос один - с чем сравнивать, как проверять. Делители "будут очень долго считать"... |
||
3 окт 19, 13:34 [21985843] Ответить | Цитировать Сообщить модератору |
Barlone Member Откуда: Сообщений: 1451 |
|
||||
3 окт 19, 13:42 [21985851] Ответить | Цитировать Сообщить модератору |
Gennadiy Usov Member Откуда: Сообщений: 2357 |
Поскольку задают вопросы, нужно привести программу в порядок: красиво оформить выходные данные. Хотя программы должно быть две (дубляж): для диапазона и для отдельного числа. |
||||
3 окт 19, 13:45 [21985856] Ответить | Цитировать Сообщить модератору |
Gennadiy Usov Member Откуда: Сообщений: 2357 |
|
||||
3 окт 19, 13:47 [21985859] Ответить | Цитировать Сообщить модератору |
Barlone Member Откуда: Сообщений: 1451 |
n = 3825123056546413051 n-1 = 21*1912561528273206525 a(n-1)/2 mod n равно 1 или n-1 для всех a от 2 до 36... |
3 окт 19, 13:51 [21985863] Ответить | Цитировать Сообщить модератору |
Gennadiy Usov Member Откуда: Сообщений: 2357 |
У меня записано: "Число А выбирается равное 10, с запасом – пока подтверждено только одно число 25326001 при а = 7. Можно увеличить число 10. Но для этого нужны проверки для чисел, больших 250 000 000." Просто увеличиваем А до 15 простых чисел! То есть до 47. И смотрим дальше. Ещё есть примеры? |
||
3 окт 19, 14:58 [21985926] Ответить | Цитировать Сообщить модератору |
Aleksandr Sharahov Member Откуда: Москва Сообщений: 2060 |
|
3 окт 19, 15:33 [21985965] Ответить | Цитировать Сообщить модератору |
Gennadiy Usov Member Откуда: Сообщений: 2357 |
Насчет простых чисел поторопился... У числа 3825123056546413051 log (n) = 42... Поэтому ставим А = 42 и рассматриваем все числа от 2 до 42. Число 36 - попадает. Ещё раз уточнил старые расчёты. Для тестовых расчётов log (1 000 000 001) = 20. Мне встречались числа 11, 13, 15. Поэтому, A = log (n). И в тесте Миллера-Рабина log (n). Однако ушли от вероятности. |
3 окт 19, 15:36 [21985967] Ответить | Цитировать Сообщить модератору |
Barlone Member Откуда: Сообщений: 1451 |
Эх, опять промахнулись... 3317044064679887385961981 - вот тут уже 43 надо. |
||
3 окт 19, 15:41 [21985973] Ответить | Цитировать Сообщить модератору |
Barlone Member Откуда: Сообщений: 1451 |
А насчет простых то как раз всё правильно: понятно, что если am mod n = 1 и bm mod n = 1 то и (ab)m mod n = 1 |
3 окт 19, 15:44 [21985979] Ответить | Цитировать Сообщить модератору |
Barlone Member Откуда: Сообщений: 1451 |
import math def jacobi(a, n): assert(a > 0 and n % 2 == 1) a %= n t = 1 while a != 0: while a % 2 == 0: a = a // 2 r = n % 8 if r == 3 or r == 5: t = -t a, n = n, a if a % 4 == 3 and n % 4 == 3: t = -t a %= n if n == 1: return t else: return 0 def pair2(a, d, n): return ((a[0] * a[0] + n - 2) % n, (a[0] * a[1]) % n) def pairmul(a, b, d, n): x = (a[0] * b[0] + d * a[1] * b[1]) % n if x % 2 == 0: x = x // 2 else: x = (n + x) // 2 y = (a[0] * b[1] + b[0] * a[1]) % n if y % 2 == 0: y = y // 2 else: y = (n + y) // 2 return (x, y) def pairpow(a, m, d, n): r = (1, 0) while m != 0: if m % 2 == 1: r = pairmul(r, a, d, n) a = pair2(a, d, n) m = m // 2 return r def isprime(n): if n == 2: return True if n % 2 == 0: return False if n == 3: return True if n % 3 == 0: return False if n == 5: return True if n % 5 == 0: return False m = int(math.sqrt(n)) if m * m == n: return False p = 3 d = p * p - 4 j = jacobi(d, n) while j == 1: p = p + 1 d = p * p - 4 j = jacobi(d, n) if j == 0: return False if pow(d, n // 2, n) != n - 1: return False a = pairpow((p, 1), (n + 1) // 2, d, n) if a[1] != 0: return False if a[0] != 1 and a[0] != n - 1: return False return TrueВот вам тест простоты на питоне, вызывать isprime(n) - проверяйте, ищите контрпримеры. Это как раз Люка. |
3 окт 19, 15:46 [21985985] Ответить | Цитировать Сообщить модератору |
Barlone Member Откуда: Сообщений: 1451 |
Точнее, один раунд |
3 окт 19, 15:53 [21985994] Ответить | Цитировать Сообщить модератору |
Barlone Member Откуда: Сообщений: 1451 |
Поторопился, если подсунуть квадрат очень большого числа, math.sqrt вычисляется с ошибкой, и в цикле поиска квадратичного невычета зависает... Поправил.import math def jacobi(a, n): assert(a > 0 and n % 2 == 1) a %= n t = 1 while a != 0: while a % 2 == 0: a = a // 2 r = n % 8 if r == 3 or r == 5: t = -t a, n = n, a if a % 4 == 3 and n % 4 == 3: t = -t a %= n if n == 1: return t else: return 0 def pair2(a, d, n): return ((a[0] * a[0] + n - 2) % n, (a[0] * a[1]) % n) def pairmul(a, b, d, n): x = (a[0] * b[0] + d * a[1] * b[1]) % n if x % 2 == 0: x = x // 2 else: x = (n + x) // 2 y = (a[0] * b[1] + b[0] * a[1]) % n if y % 2 == 0: y = y // 2 else: y = (n + y) // 2 return (x, y) def pairpow(a, m, d, n): r = (1, 0) while m != 0: if m % 2 == 1: r = pairmul(r, a, d, n) a = pair2(a, d, n) m = m // 2 return r def isprime(n): if n == 2: return True if n % 2 == 0: return False if n == 3: return True if n % 3 == 0: return False if n == 5: return True if n % 5 == 0: return False m = int(math.sqrt(n)) if m * m == n: return False k = (m + n // m) // 2 while k != m: m, k = k, (m + n // m) // 2 if m * m == n: return False p = 3 d = p * p - 4 j = jacobi(d, n) while j == 1: p = p + 1 d = p * p - 4 j = jacobi(d, n) if j == 0: return False if pow(d, n // 2, n) != n - 1: return False a = pairpow((p, 1), (n + 1) // 2, d, n) if a[1] != 0: return False if a[0] != 1 and a[0] != n - 1: return False return True n = 3317044064679887385961981 m = n // 2 print(isprime(3317044064679887385961981*3317044064679887385961981)) #for i in range (2, 44): # print (i, pow(i,m,n), jacobi(i,n)) |
3 окт 19, 16:10 [21986008] Ответить | Цитировать Сообщить модератору |
Barlone Member Откуда: Сообщений: 1451 |
С куском отладочного кода в конце :) |
3 окт 19, 16:13 [21986011] Ответить | Цитировать Сообщить модератору |
Gennadiy Usov Member Откуда: Сообщений: 2357 |
Здесь s = 2. При s = 1 одни 1 и (n - 1) до 42. А при s = 0 при 2 сразу составное! |
||
3 окт 19, 16:23 [21986019] Ответить | Цитировать Сообщить модератору |
Gennadiy Usov Member Откуда: Сообщений: 2357 |
А если пройтись по всем нечётным, где s = 1, и считать 1 и (n - 1) до "выбывания"? |
||
3 окт 19, 16:32 [21986033] Ответить | Цитировать Сообщить модератору |
mayton Member Откуда: loopback Сообщений: 51153 |
В нашем случае это норм вариант. Тут-же принципиальная возможность изучается. Перформанс - второе дело. Тем более что для Питона есть библиотеки поддержки длинных. |
||||
3 окт 19, 16:45 [21986047] Ответить | Цитировать Сообщить модератору |
Топик располагается на нескольких страницах: ←Ctrl назад 1 2 3 4 5 6 [7] 8 9 10 вперед Ctrl→ все |
Все форумы / Программирование | ![]() |