ReSQL.ru
     
powered by simpleCommunicator - 2.0.49     © 2025 Programmizd 02
Мобильная версия    Контакт    Правила    FAQ    Помощь
Доб. в избранное | Игнор. тему | Прикреп. тему | Пометить прочит. / непрочит. | Фильтр
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Эвристический алгоритм (формула, тест простоты) для определения простых чисел
25 сообщений из 233, страница 9 из 10
  9  все
Эвристический алгоритм (формула, тест простоты) для определения простых чисел
    #39871747
Barlone
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Barlone
Участник
Gennadiy UsovА вот интересная задача (по поводу определения раундов)

import math
a1= math.sqrt(1000000000000000000000001)//1
a2 = math.sqrt(1000000000000000000000000000000000000000000001)//1
print (a1, a2)

И печать результатов:

(1000000000000.0, 3.1622776601683792e+22)

Вот почему одно число целое, а другое число вещественное?А черт его знает, надо в исходники питона смотреть.
Вот вам целочисленный корень:
Код: python
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
def intsqrt(n):
    q = n.bit_length()
    if q <= 129:
        m = int(math.sqrt(n))
    else:
        k = (q - 128) >> 1
        m = int(math.sqrt(n >> (2*k))) << k
    k = (m + n // m) >> 1
    while k != m:
        m, k = k, (m + n // m) >> 1
    return k
...
Рейтинг: 0 / 0
04.10.2019, 16:12
| Ответить | Цитировать | Написать  
Эвристический алгоритм (формула, тест простоты) для определения простых чисел
    #39871751
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Gennadiy Usov
Гость
Спасибо!

Сейчас попробую
...
Рейтинг: 0 / 0
04.10.2019, 16:16
| Ответить | Цитировать | Написать  
Эвристический алгоритм (формула, тест простоты) для определения простых чисел
    #39871756
Barlone
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Barlone
Участник
Gennadiy UsovА вот интересная задача (по поводу определения раундов)

import math
a1= math.sqrt(1000000000000000000000001)//1
a2 = math.sqrt(1000000000000000000000000000000000000000000001)//1
print (a1, a2)

И печать результатов:

(1000000000000.0, 3.1622776601683792e+22)

Вот почему одно число целое, а другое число вещественное?А вообще-то первое тоже вещественное - там же в конце ".0".
Просто во втором нечетное количество ноликов, и в 52 бита (точность мантиссы в double) оно не лезет, поэтому в экспоненциальной форме
...
Рейтинг: 0 / 0
04.10.2019, 16:25
| Ответить | Цитировать | Написать  
Эвристический алгоритм (формула, тест простоты) для определения простых чисел
    #39871834
Barlone
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Barlone
Участник
BarloneЧто-то у меня на диапазоне 200000 с 2 2048 нашлось 151 число. Черт возьми, надо было их вывести, а не просто посчитать.Перепроверил, на 60 раундов Соловея-Штрассена, все простые:
 
2 2048 +...
(981,1617,3063,3211,4143,7405,9843,10665,10725,11097,11467,13137,13333,15703,17001,
17787,18523,21397,24963,25405,26697,26935,30475,31627,34005,34431,35281,35763,36535,
37653,38841,39825,42637,43965,44281,45303,46303,46995,49957,54613,54873,57325,62847,
65377,65545,67701,67953,68415,68535,68941,69493,69543,72207,75775,76413,76647,77797,
78003,81081,81093,81795,83335,83593,84397,84463,89023,89835,89965,90127,90147,90993,
93795,94593,97455,97707,98077,99867,99945,100431,105435,107025,107385,107851,109197,
111343,115911,115941,116667,117601,123327,124381,125523,129051,130453,130551,130773,
131203,131301,131877,132915,133221,133651,134085,135751,135771,136383,136711,137443,
141901,147783,148455,150997,152751,153097,153817,155013,155191,156027,156057,157543,
160747,162385,162747,162891,164191,166843,167001,172603,173373,174157,175503,176563,
180081,182811,183397,184021,184167,186235,187017,187803,192091,192883,193107,193635,
193831,194205,195321,196261,197587,198213,199425)
...
Рейтинг: 0 / 0
04.10.2019, 18:11
| Ответить | Цитировать | Написать  
Эвристический алгоритм (формула, тест простоты) для определения простых чисел
    #39871837
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Надо базу вести. Типа "Простые числа по версии Соловея-Штрассена". Потом еще базу. Простые по версии Усова.
...
Рейтинг: 0 / 0
04.10.2019, 18:14
| Ответить | Цитировать | Написать  
Эвристический алгоритм (формула, тест простоты) для определения простых чисел
    #39871983
Barlone
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Barlone
Участник
Прогнал через свой вариант теста все числа до 2 32 . Количество найденных простых совпало с количеством простых, полученных решетом. Также сравнил список до 2 24 . Ничего лишнего, ничего не пропущено.
...
Рейтинг: 0 / 0
05.10.2019, 07:06
| Ответить | Цитировать | Написать  
Эвристический алгоритм (формула, тест простоты) для определения простых чисел
    #39872002
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Gennadiy Usov
Гость
Попробовал перейти на раунды.
Пусть раунд - это обращение к основной формуле: pow(a1, t2, p).
Все остальные операторы не так затратны по времени, особенно для больших чисел.
Тогда:

-проверка чисел от- 5 -до - 1000005
-количество простых чисел- 78497
-количество раундов - 3482972
-минимальное количество раундов для числа - 1
-количество минимальных раундов - 421362
-максимальное количество раундов для числа - 39
...
Рейтинг: 0 / 0
05.10.2019, 11:19
| Ответить | Цитировать | Написать  
Эвристический алгоритм (формула, тест простоты) для определения простых чисел
    #39872007
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Gennadiy Usov
Гость
Далее, ещё интереснее.

Пусть ограничитель для проверки числа 39 раундов.
Для чисел после 2**1024-1 в количестве 10000 получается следующая картинка:

2019-10-05-12.59.02
-количество простых чисел- 14
-количество раундов - 1733
-минимальное количество раундов для числа - 1
-количество минимальных раундов - 1185
-максимальное количество раундов для числа - 39
-количество максимальных раундов - 546
-остаток- 2
2019-10-05-12.59.27

То есть, программа либо сразу сообщает, что число составное, либо все 39 раундов для простого числа.
И всего 2 раунда на более сложную проверку.
...
Рейтинг: 0 / 0
05.10.2019, 13:11
| Ответить | Цитировать | Написать  
Эвристический алгоритм (формула, тест простоты) для определения простых чисел
    #39872076
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Gennadiy Usov
Гость
Небольшое уточнение.

В предыдущем сообщении представлена распечатка работы программы, когда имеются делители до 100.

Та же программа, в которой нет делителей, выдаёт следующий результат:

-количество простых чисел- 14
-количество раундов - 5520
-минимальное количество раундов для числа - 1
-количество минимальных раундов - 4986
-максимальное количество раундов для числа - 38
-количество максимальных раундов - 532
-остаток- 2
...
Рейтинг: 0 / 0
05.10.2019, 20:26
| Ответить | Цитировать | Написать  
Эвристический алгоритм (формула, тест простоты) для определения простых чисел
    #39872101
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Интересно. Во главе угла криптографии стоит операция деления. как некий бастион
который ограничивает перформанс криптоанализа. Что-бы мы не делали а эта
операция в стеке - принципиально не оптимизируема. Я думал о машинной реализации.
Судя по описаниям она принципиально не отличается от классического деления в столбик
с той разницей что работает двоичная логика вычитаний. И я подумал - а какую собсвенно
пользу можно извлечь из результата деления. В классическом варианте любая операция
машинного деления на самом деле делает больше. Она фиксирует остаток. Кроме
того если мы используем делители достаточно длинные по разрядной сетке но имеющие
вид последовательности простых то делители не будут сильно отличаться. Фактически
от шага к шагу меняются младшие разряды делителя.
...
Рейтинг: 0 / 0
05.10.2019, 22:10
| Ответить | Цитировать | Написать  
Эвристический алгоритм (формула, тест простоты) для определения простых чисел
    #39872138
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Gennadiy Usov
Гость
Ещё пример работы программы:

Пусть ограничитель для проверки числа 39 раундов.
Для чисел после 2**2048-1 в количестве 10000 получается следующая картинка:

-количество простых чисел- 7
-количество раундов - 5261
-минимальное количество раундов для числа - 1
-количество минимальных раундов - 4993
-максимальное количество раундов для числа - 38
-количество максимальных раундов - 266
-остаток- 2
...
Рейтинг: 0 / 0
06.10.2019, 06:26
| Ответить | Цитировать | Написать  
Эвристический алгоритм (формула, тест простоты) для определения простых чисел
    #39872238
Barlone
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Barlone
Участник
Далеко не для каждого составного числа найдется "свидетель простоты" по Рабину-Миллеру, то есть основание, по которому это число будет псевдопростым. На самом деле, такие составные числа, для которых существует хотя бы один свидетель простоты, довольно редки. Но уж если один свидетель простоты существует для некоего составного числа, то их (свидетелей) для этого числа обязательно будет несколько: все они будут корнями какой-то степени из единицы по модулю одного из делителей этого составного числа. Вот именно потому, что свидетели простоты по Миллеру-Рабину всегда появляются пачками, выгоднее не гонять кучу раундов, а использовать другой, независимый тест Люка, который опирается не на мультипликативную группу вычетов, а на другую группу.
...
Рейтинг: 0 / 0
06.10.2019, 17:59
| Ответить | Цитировать | Написать  
Эвристический алгоритм (формула, тест простоты) для определения простых чисел
    #39872240
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Gennadiy Usov
Гость
BarloneДалеко не для каждого составного числа найдется "свидетель простоты" по Рабину-Миллеру, то есть основание, по которому это число будет псевдопростым. На самом деле, такие составные числа, для которых существует хотя бы один свидетель простоты, довольно редки. Но уж если один свидетель простоты существует для некоего составного числа, то их (свидетелей) для этого числа обязательно будет несколько: все они будут корнями какой-то степени из единицы по модулю одного из делителей этого составного числа. Вот именно потому, что свидетели простоты по Миллеру-Рабину всегда появляются пачками, выгоднее не гонять кучу раундов, а использовать другой, независимый тест Люка, который опирается не на мультипликативную группу вычетов, а на другую группу.Тест Люка тоже выполняет серию раундов (основание степени, степень, модуль).
Почему нельзя посчитать количество этих раундов для различных чисел?

Тест Люка вероятностный, следовательно, получаются псевдопростые числа.
...
Рейтинг: 0 / 0
06.10.2019, 18:15
| Ответить | Цитировать | Написать  
Эвристический алгоритм (формула, тест простоты) для определения простых чисел
    #39872261
Barlone
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Barlone
Участник
Конечно тест Люка вероятностный. Я вообще не про то.
Вот есть списки сильных псевдопростых чисел по разным основаниям. Так вот, далеко не каждое число попадет хотя бы в один такой список. Ну то есть, можно перебрать например все составные нечетные числа n от 15 до 9999, и для каждого перебрать все основания от 2 до n-2 и провести тест Миллера-Рабина. Получить список составных чисел, являющихся псевдопростыми хотя бы по одному основанию.
Потом получить аналогичный список для теста Люка - то есть провести тест по всем вариантам параметров, которые могут использоваться для этого теста, и выписать псевдопростые по Люка хотя бы по одному варианту параметров.
А потом проверить, есть ли в этих двух списках совпадения.
...
Рейтинг: 0 / 0
06.10.2019, 19:49
| Ответить | Цитировать | Написать  
Эвристический алгоритм (формула, тест простоты) для определения простых чисел
    #39872265
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Gennadiy Usov
Гость
BarloneКонечно тест Люка вероятностный. Я вообще не про то.
...
можно перебрать например все составные нечетные числа n от 15 до 9999, и для каждого перебрать все основания от 2 до n-2 и провести тест Миллера-Рабина. Получить список составных чисел, являющихся псевдопростыми хотя бы по одному основанию.
Потом получить аналогичный список для теста Люка - то есть провести тест по всем вариантам параметров, которые могут использоваться для этого теста, и выписать псевдопростые по Люка хотя бы по одному варианту параметров.
А потом проверить, есть ли в этих двух списках совпадения. Есть два варианта: совпадают и не совпадают.
А что дальше?

Надо говорить об этом.
...
Рейтинг: 0 / 0
06.10.2019, 20:00
| Ответить | Цитировать | Написать  
Эвристический алгоритм (формула, тест простоты) для определения простых чисел
    #39872293
Barlone
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Barlone
Участник
Gennadiy UsovBarloneКонечно тест Люка вероятностный. Я вообще не про то.
...
можно перебрать например все составные нечетные числа n от 15 до 9999, и для каждого перебрать все основания от 2 до n-2 и провести тест Миллера-Рабина. Получить список составных чисел, являющихся псевдопростыми хотя бы по одному основанию.
Потом получить аналогичный список для теста Люка - то есть провести тест по всем вариантам параметров, которые могут использоваться для этого теста, и выписать псевдопростые по Люка хотя бы по одному варианту параметров.
А потом проверить, есть ли в этих двух списках совпадения. Есть два варианта: совпадают и не совпадают.
А что дальше?

Надо говорить об этом.Есть гипотеза, что совпадений не будет.
...
Рейтинг: 0 / 0
06.10.2019, 20:44
| Ответить | Цитировать | Написать  
Эвристический алгоритм (формула, тест простоты) для определения простых чисел
    #39872301
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Gennadiy Usov
Гость
BarloneGennadiy Usov Есть два варианта: совпадают и не совпадают.
А что дальше?
Надо говорить об этом.Есть гипотеза, что совпадений не будет.Кто бы сомневался.

Если не совпадает, то что делать?
...
Рейтинг: 0 / 0
06.10.2019, 20:57
| Ответить | Цитировать | Написать  
Эвристический алгоритм (формула, тест простоты) для определения простых чисел
    #39874074
exp98
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
exp98
Участник
BarloneЧто-то у меня на диапазоне 200000 с 2 2048 нашлось 151 число. А ты мне отвечал, что долго считать. За это личное спасибо.
Может всё же сочтёшь кол-во персонально для меня ещё диапазончик
2^4096 +500000, предварительная оценка [ 176,05 + - 13,268 ] ??
Вроде не намного и дольше считать, раз в 5-6 ... я думаю. Мне только кол-во.
...
Рейтинг: 0 / 0
09.10.2019, 14:53
| Ответить | Цитировать | Написать  
Эвристический алгоритм (формула, тест простоты) для определения простых чисел
    #39877671
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Gennadiy Usov
Гость
maytonGennadiy Usov, я несколько раз обращался к тебе с просьбой собрать отклик твоего кода через равные
промежутки интервалов. Я хотел построить график. И по нему оценить асимптоматику. Это важно.
Важные даже не числа а форма графика. Парабола. Экспонента. Или x в степени x как некая ссылка
на комбинаторную сложность. Но мне показалось что данные у тебя беспорядочны и их мало и я отбросил
эту затею.Насколько я помню, последними таблицами были 21976531 и 21982245 .
В последнем сообщении была фраза:maytonДобавил 100 тысяч на диапазоне 2048 бит.
Вот данные для проверки. Две таблички надо соединить. Но уже поздно. Я засыпаю.А далее - maytonЯ говорю табличку заполните.В табличках есть параметры:
диапазон, количество простых чисел и время работы программы на диапазоне.

Спрашивается: каких параметров не хватает?
...
Рейтинг: 0 / 0
17.10.2019, 13:27
| Ответить | Цитировать | Написать  
Эвристический алгоритм (формула, тест простоты) для определения простых чисел
    #39888735
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Gennadiy Usov
Гость
Barlone
Gennadiy UsovBarloneИщем простые от 2^1024 - нашлись 2^1024 + (643, 1081, 2113, 2715, 3711)
Ещё 5335, 5793, 5947, 7015, 7447, 7935, 8953, 8995, 9855.
1 мин. 48 сек.У меня секунд за 15 те же.На каждом ПК и на каждом языке программирования свои скорости.

В работе 22011445 рассматривался эвристический алгоритм для определения простых чисел в окрестности чисел Mn = 2^n – 1.

Кроме того, была проведена оценка размера таких окрестностей
с точки зрения отсутствия возможности получения составных чисел при работе эвристического алгоритма.
Поэтому для чисел 2^1024-1 и 2^2048-1 размер такой окрестности будет составлять намного больше, чем 10000 чисел.
Следовательно, в этой окрестности при рассмотрении очередного числа достаточно одно вычисление вида «pow».
Допустим, это "рабочий диапазон".

Для чисел 2^1024-1 и 2^2048-1 рабочий диапазон имеет место как со знаком +, так и со знаком -.

Исследования на ПК для диапазона из 10000 чисел показали, что:
для знака + эвристический алгоритм работает на 4% медленнее оператора pow.
для знака - эвристический алгоритм работает на 3% быстрее оператора pow.

Вне рабочего диапазона (например, очень далеко от чисел 2^1024-1 и 2^2048-1), по всей видимости,
необходимо несколько проверок вида «pow».
...
Рейтинг: 0 / 0
13.11.2019, 16:40
| Ответить | Цитировать | Написать  
Эвристический алгоритм (формула, тест простоты) для определения простых чисел
    #39889990
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Gennadiy Usov
Гость
Gennadiy Usov
Следовательно, в этой окрестности при рассмотрении очередного числа достаточно одно вычисление вида «pow».
Допустим, это "рабочий диапазон".
...
Вне рабочего диапазона (например, очень далеко от чисел 2^1024-1 и 2^2048-1), по всей видимости,
необходимо несколько проверок вида «pow».
Конечно, необходимо заметить, что исследования проводились для "pow(3,", или для pow3.

Поэтому, если нужно быстро найти простые числа, то можно их найти в так называемом "рабочем диапазоне" от числа Мерсенна.
И для этого достаточно одно обращение к pow3.

Вне "рабочего диапазона" потребуется уже несколько обращений к pow3,
или несколько обращений к операторам pow с другим основанием степени.

При этом напоминаю, что для чисел Mnk, у которых k кратно 4, "рабочий диапазон" будет намного больше,
чем для остальных чисел Mnk.
...
Рейтинг: 0 / 0
16.11.2019, 09:42
| Ответить | Цитировать | Написать  
Эвристический алгоритм (формула, тест простоты) для определения простых чисел
    #39890105
exp98
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
exp98
Участник
Прошу тебя, друг Аркадий Геннадий, не говори красиво!(цэ):
Gennadiy Usov
Кроме того, была проведена оценка размера таких окрестностей с точки зрения отсутствия возможности получения составных чисел при работе эвристического алгоритма.

Почти ничего не понял в ваших словах, но благодаря следущей строчке:
Gennadiy Usov
Поэтому для чисел 2^1024-1 и 2^2048-1 размер такой окрестности будет составлять намного больше, чем 10000 чисел.
решил прикинуть по науке. Фразу "отсутствия возможности получения составных" интерпретировал как диапазон, гарантирующий (с хорошей долей вероятности) наличие хоть 1 простого. Оценивал на бумажке. Почему-то у меня не получается "намного больше, чем 10000".
Наоборот, если исходить из прикида, что на дальности 1млн от 2^2K кол-во простых можно оценить как наиболее вероятный интервал 72тыс +- 268, то тогда уже на дальности 3620 весьма вероятно 1 простое. А на дальности 10тыс их весьма вероятно 5.
Соответственно, ведя отсчёт от 2^K, в 10тыс поместится простых 11-12 штук.
Кстати другим способом на дальности 10тыс от 2^K их оценивается 14.4 +- 4.
К сож, теорвер не позволяет мне оценить точнее малые кол-ва (точнее конечно будет не на бумажке).

Я это всё к тому, что как-то не понятна фраза про "намного больше, чем 10000".
...
Рейтинг: 0 / 0
17.11.2019, 00:09
| Ответить | Цитировать | Написать  
Эвристический алгоритм (формула, тест простоты) для определения простых чисел
    #39890129
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Gennadiy Usov
Гость
exp98
Фразу "отсутствия возможности получения составных" интерпретировал как диапазон, гарантирующий (с хорошей долей вероятности) наличие хоть 1 простого. Оценивал на бумажке. Почему-то у меня не получается "намного больше, чем 10000".
Рабочий диапазон есть диапазон чисел,
где эвристический алгоритм определяет сколько угодно чисел, которые будут простыми числами,
причём ни одно из определённых чисел не будет составным числом.
...
Рейтинг: 0 / 0
17.11.2019, 07:52
| Ответить | Цитировать | Написать  
Эвристический алгоритм (формула, тест простоты) для определения простых чисел
    #39890200
exp98
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
exp98
Участник
авторРабочий диапазон есть диапазон чисел, где эвристический алгоритм определяет сколько угодно чисел, которые будут простыми числами, причём ни одно из определённых чисел не будет составным числом. Видите, даже попытка разъяснить боле-мене конкретный вопрос, всё равно приводит к двусмысленности.
Писать по-русски ведь тоже ещё уметь надо. Тем более технический текст. Обычно почему-то полагается, что читатель проделал к этому моменту тот же самый мыслительный путь, и важно, что остановился на том же самом месте, что и писатель.
И тогда целиком воспроизводится ситуация анекдота: "Да пошла ты наф со своим утюгом!"

Однако практически всегда это не так. Но такой писатель никогда не оценивает со стороны, как писанина будет воспринята. Это не только ваша особенность, большинство прогеров так же пишут.
То же самое относится к вашей самооценке правильности собственной программы, сам сделал, сам написал и ку-ка-ре-ку. А вы все верьте.

Я уже не говорю о спец. подборе слов для выражения мысли ... Как же меня задрали за всю жизнь эти "постановщики задач", приходят и начаинают с "прерваного места". И вы ещё тут ... вот почти и не читаю, но только прочту, блин ... А попытка одной фразой ответиь на неск. вопросов ?..

Вашу двусмысленность наверное (я лищь предполагаю) можно было бы ликвидировать. Но "сколько угодно чисел", да ещё "которые будут простыми" ... наверное это бесконечность, да? впихнутая в конечный диапазон!

Как вариант: РД есть диапазон чисел, в к-ром ЭАGUОПЧ безошибочно определяет любое составное число как составное.

И всё равно остаётся необъяснённым вопрос, не пропускает ли ЭА при этом ПЧ, ошибочно принимая их за составное? (о том, что некто некогда как-то где-то это проверял, я наслышан)
...
Рейтинг: 0 / 0
17.11.2019, 17:36
| Ответить | Цитировать | Написать  
Эвристический алгоритм (формула, тест простоты) для определения простых чисел
    #39890203
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Gennadiy Usov
Гость
exp98
авторРабочий диапазон есть диапазон чисел, где эвристический алгоритм определяет сколько угодно чисел, которые будут простыми числами, причём ни одно из определённых чисел не будет составным числом.
Как вариант: РД есть диапазон чисел, в к-ром ЭАGUОПЧ (других эвристических алгоритмов пока нет)
безошибочно определяет любое составное число как составное.Наверное, так будет проще для читателя.

Хотя, любой тест простоты определяет простоту чисел,
то есть, "отсекает" составные числа.
exp98
И всё равно остаётся необъяснённым вопрос, не пропускает ли ЭА при этом ПЧ, ошибочно принимая их за составное? (о том, что некто некогда как-то где-то это проверял, я наслышан)
А всё очень просто. Перебор делителей.
Поэтому на моём ПК получается проверить только до 2^32-1 +k.

А дальше - эвристика... Хотите верьте, хотите нет.
...
Рейтинг: 0 / 0
17.11.2019, 18:18
| Ответить | Цитировать | Написать  
25 сообщений из 233, страница 9 из 10
  9  все
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Эвристический алгоритм (формула, тест простоты) для определения простых чисел
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
Польз. соглашение
NoSQL.ru       Новости, Чат       Фотоальбом: Участники, Встречи
Закрыть
start [/forum/topic.php?fid=16&msg=39871983&tid=1339873]:
 0ms
get settings:
 10ms
get forum list:
 13ms
check forum access:
 3ms
check topic access:
 3ms
track hit:
 167ms
get topic data:
 10ms
get forum data:
 3ms
get page messages:
 66ms
get tp. blocked users:
 2ms
others: 244ms
total:  521ms
созд. / загр.: 521ms
x
x
Закрыть


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