Алгоритм поиска целых простых чисел

Предлагаю простой алгоритм проверки и поиска простых чисел, приглашаю к сотрудничеству в написании программы для его реализации, демонстрация его работы показана в прилагаемом файле.

Вложения

algo2.xls (45.0 Кб, 21 просмотров)

0

Какая-то непонятная демонстрация работы алгоритма.

Например, мне показалось, что это демонстрация проверки на простоту чисел до 25. Около проверяемого числа справа отображена таблица, которая вероятно, каким-то образом рассчитывается, и по ней решается простое это число или нет. Но количество элементов в этой таблице намного больше самого проверяемого числа! Т.е. сложность такого алгоритма (количество операций) становится слишком большой даже по сравнению с обычной проверкой на простоту (проверка всех возможных делителей числа).

0

Для уточнения алгоритма прилагаю файл "Демонстрация" .
Действительно анализируемые массивы растут очень быстро, но следует учесть, что большую часть массивов составляют нули, которые при сравнении массивов могут быть при соответствующей программе пропущены алгоритм может оказаться очень быстрым, так как в нем использованы две простые операции сдвига и и сравнения.

Программа для его реализации может состоять из трех блоков:
- подготовка исходного массива 1;
- сдвиг его на проверяемое число и получение массива 2;
- программа мониторинга совпадений 1 в массиве 1 и массиве 2, в которой можно осуществить пропуски из рассмотрения нулей в сравниваемых массивах.
Если совпадение единиц в массивах оказывается единственным, то проверяемое число простое

Вложения

Демонстрация.xls (66.0 Кб, 17 просмотров)

0

Сообщение от Баженов Действительно анализируемые массивы растут очень быстро, но следует учесть, что большую часть массивов составляют нули

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

Т.е. для проверки числа 25, даже если мы отбросим работу с "нулями", нам нужно пробежаться по 25 "единицам". Т.е. для проверки N, нужно совершить действий. Но обычный простой алгоритм проверки делителей имеет сложность

Да, скорость выполнения сдвигов и сравнений много выше, чем операции деления. Но, для больших чисел алгоритм с меньшей сложностью будет все равно быстрее.

0

Возможно значительное ускорение, хочется надеется, работы данного алгоритма при одновременной его работе на нескольких ЭВМ и переводе данных массивов в формат байтов, при котором проявляется ярко выраженная цикличность в чередовании одинаковых байтов. В любом случае для достаточно больших проверяемых чисел этот алгоритм должен быть быстрее стандартного решета, упомянутого Вами. К сожалению, вопрос размерности сравниваемых массивов отпугивает желающих его программной реализации. Хотя для аналогии я бы мог привести
сравнение с движением простого пассажирского поезда и экспресса, при движении которого большую часть станций он проходит без остановок, а оставшиеся с минимальным временем остановок. Сравните время деления большого числа хотя бы на 3 и временем сравнения соответствующего, пусть даже большого, числа единиц.
У меня остается уверенность в том, что при достаточном профессионализме программиста данный алгоритм окажется самым быстрым. Это подтверждается тем, что им уже интересуются те, кто связан с работами по криптографической защите информации. Кроме того, созданный на его основе метод спектрального анализа цифрового сообщения позволяет определить все простые числа, использованные при его криптографической защите. К сожалению в такой перспективе мне не удается убедить заинтересованные лица.
В прошлое время я занимался оптическим и ядерным спектральным анализом, которые позволяют по спектру определять из каких элементов состоит исследуемый образец.
Приношу извинения за время, которое я отнял у Вас.
Мне очень жаль, что описанные мною перспективы ни кем пока не осознаны.
В качестве дополнительного его применения также возможно с его помощью определять все тройки Пифагоровых чисел.

1

Баженов
У вас довольно интересное отношение к простым числам.
Но вот, если вам интересно, то я дам вам идею по простым
числам, когда мне они потребовались в одной задаче...
...
Мне нужно было в одной программе 100 миллионов простых чисел.
Я написал вспомогательную программу и она создала файл прямого
доступа заполнив его простыми числами (каждое число 4 байта, итого
400 миллионов байт - это ровно 100 миллионов простых чисел)
Вы понимаете, поскольку числа были предварительно вычислены,
то их достаточно было просто считать с файла и использовать в программе
Это были только простые числа. Они в проверке не нуждались и программа
работала достаточно быстро...

0

1. Алгоритм работает

Давайте разберем Ваш алгоритм. Имеется две строки в excel:
в верхней строке - единицы стоят около каждого числа, являющегося квадратом
в нижней строке - таже верхняя строка, но сдвинутая на n (на анализируемое число)

Если верхнее число обозначить как , а нижнее как , где -анализируемое число, то единицы совпадают, когда верхнее и нижнее числа будут равны друг другу.


Отсюда следует, что и являются множителями числа n. Т.е. если единицы в строках совпадут, то это значит, что анализируемое число составное (конечно, необходимо исключить вариант ). Т.е. Вы правы, Ваш алгоритм позволит определять простоту числа.

2. Реализация алгоритма

Для расчета эти двух строк, нам нужно:
- научиться строить верхний ряд квадратов (1, 4, 9, 16 ...)
- научиться строить нижний ряд - опять квадраты + фиксированное число
- сравнивать эти два ряда (пока не найдется общий элемент в двух рядах)

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

Поэтому длина массива - вовсе не проблема с точки зрения памяти! Нет необходимости превращать их в биты, или еще каким-либо образом сжимать

3. Проблемы

Но! Нам все равно придется сгенерировать числа из каждого ряда. В Вашей аналогии - расставить единицы в каждой строчке таблицы. Действительно, для генерации этих чисел достаточно использовать только операции сложения, т.е. не будем умножать и делить. Но этих чисел слишком много.

Сколько же этих чисел придется сгенерировать?

Мы уже говорили, что единицы совпадут, если . Причем - количество единиц в верхнем ряду, а - количество единиц в нижнем. Когда единицы совпадут, то мы к этому времени сгенерируем квадратных чисел (единиц в excel). Также глядя на выражение можно заметить, что при разложении числа n на два множителя выражение является большим из этих множителей.

Для примера возьмем число 21 = 3 * 7, значит для его проверки Вам придется сгенерировать (проставить единицы в excel) 7 чисел (больший множитель). Проверьте, по таблице, это действительно так. В общем, случае для n = 3x, придется сгенерировать x чисел, где x=n/3. Т.е. количество чисел, с которыми нам придется работать равно самому числу, деленную на некоторую константу, которая достаточно мала по сравнению с очень большим числом n. А вот при простой проверке достаточно проверить деление числа 21 на числа от 1 до 4 (до корня из 21), т.е. всего 4 числа.

И чем больше n, тем больше эта разница будет возрастать. Для n = 10^10, Ваш алгоритм выполнит ~ 3*10^9 операций, а обычная проверка всего 10^5, т.е. окажется в более 10^4 раз быстрее. Даже если операция деления будет в сто раз медленнее, Ваш алгоритм будет все равно медленнее. Потому что у Вас больше количество операций - у Вас , а в обычно алгоритме .

Если Вам попадется простое число , то Вам придется "проверить" единиц, а обычному алгоритму, опять все те же . Для 23 - у вас проверка 23 единиц, а в обычном алгоритме 4 деления (умножения)

P.S. Ускорение на нескольких ЭВМ даст улучшение в разы, а отставание от других алгоритмов у Вас на порядки. Возможно когда-нибудь Вы найдете эффективный алгоритм проверки на простоту, но, к сожалению, алгоритм в таком виде неэффективен

А для Пифагоровых троек имеется формула: любая пара чисел задаёт примитивную пифагорову тройку

4

Хочу порадовать Вас успехом применения указанного алгоритма поиска простых чисел. Программа, написанная на его основе начинающим программистом показывает превосходные результаты по быстродействию, буду работать с ним и далее по ее совершенствованию. Если у Вас появятся конкретные предложения по совершенствованию алгоритма, мы готовы их рассмотреть. Уверяю Вас, что другого пути поиска простых чисел сравнимого по быстродействию не существует. Поиску их я отдал уже много лет. Все они удовлетворительно работали до определенной достаточно большой величины проверяемого числа. Предлагаемый алгоритм тащит свои вагоны до самого конца с минимальными остановками, но гарантированно дотащит.

0

Сообщение от Баженов Уверяю Вас

Я думаю, что вы заблуждаетесь. Но тесты скажут лучше любых уверений и расставят все по своим местам. Напишите пример какого-нибудь N-го по счету простого числа и за сколько времени работы программы вы его нашли.

1

Сообщение от Баженов Хочу порадовать Вас успехом применения указанного алгоритма поиска простых чисел

Было бы здорово увидеть конкретные результаты, подтверждающие высокое быстродействие предложенного алгоритма и/или его реализации.

1

Мне было бы интересно узнать, сколько времени потребуется, чтобы дополнить упомянутую Вами таблицу простых чисел хотя бы еще одним новым простым числом.
Все читающие эти строки не видят почему-то, что данный алгоритм позволяет в исследуемой числовой последовательности определить те простые числа, которые были использованы в его создании, то есть возможности его применения для спектрального анализа цифрового сообщения и последующей его расшифровки.


Что является интересной и перспективной темой для исследования указанного метода.

Добавлено через 30 минут
Если бы даже я имел достаточно хороший результат, то по известным причинам я бы не смог им с Вами поделиться.
Мои знания в технике программирования не распространены далее простого варианта Visual Basic.
Единственное, что мне хорошо понятно, это перспективы применения данного метода при его достаточно умелом использовании.

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

0

Уважаемый Баженов,

Сообщение от Баженов Мне было бы интересно узнать, сколько времени потребуется, чтобы дополнить упомянутую Вами таблицу простых чисел хотя бы еще одним новым простым числом.

Убедительная просьба, указывать к какому собеседнику относится вопрос (вероятно это вопрос к echs). Это легко сделать кликнув на имени пользователя слева от сообщения, и его имя добавится в текст Вашего сообщения.

И если не ошибаюсь Ваш алгоритм тоже не позволяет искать "следующее простое число". Или все же ошибаюсь?

Сообщение от Баженов Все читающие эти строки не видят почему-то, что данный алгоритм позволяет в исследуемой числовой последовательности определить те простые числа, которые были использованы в его создании, то есть возможности его применения для спектрального анализа цифрового сообщения и последующей его расшифровки.

К своему стыду, мне ничего не известно про упоминаемый Вами "спектральный анализ цифрового сообщения"? Может быть в свете такого анализа удастся посмотреть на Ваш алгоритм с другой точки зрения. Укажите, пожалуйста, какие-нибудь ссылки или ключевые слова для поиска.

Сообщение от Баженов Если бы даже я имел достаточно хороший результат, то по известным причинам я бы не смог им с Вами поделиться. Мои знания в технике программирования не распространены далее простого варианта Visual Basic. Единственное, что мне хорошо понятно, это перспективы применения данного метода при его достаточно умелом использовании.

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

Для ускорения Вашего метода я рекомендую подумать о том, как можно "перескакивать" некоторые единицы в Вашей таблице. Например при проверке простоты числа 21 (см. таблицу) после проверки столбца 16 перейти сразу к проверке столбца 49, т.е. перескочить единицы в столбцах 19, 20, 23, 25, 28, 35 и т.д. Т.е. нужно добавить к алгоритму какие-то правила, которые позволят не "останавливаться" на каждой единице в Вашей таблице, а идти более крупными шагами, "угадывая", что внутри этого шага уж точно не встретятся совпадения единиц. Если такие шаги окажутся достаточно большими, то алгоритм может стать быстрым.

0

Предлагаю разработанные мною таблицы умножения, которые содержат нечетные числа разлагаемые на сомножители.
Эти таблицы также могут быть использованы для проверки простых чисел.
Если проверяемое число отсутствует в соответствующих таблицах, то оно гарантированно является простым числом.
Таблицы обладают периодическими свойствами по вертикали и горизонтали и поэтому могут быть легко расширены.

Вложения

Таблицы умножения.xls (100.0 Кб, 9 просмотров)

0

Сообщение от Баженов Предлагаю простой алгоритм проверки и поиска простых чисел

Я так понял, что цель алгоритма - не просто проверить число на простоту, а найти все простые от 1 до какого то верхнего предела, так? Тогда сложность алгоритма уместнее сравнивать не со сложностью перебора делителей , а, например, со сложностью решета Аткина.

0

В pdf - математические трюки, точнее - арифметические. Возможно, будет интересно.

Вложения

Matematicheskie_tryuki_dlya_bystrogo_schyota_2018_Fogt_I.pdf (1.57 Мб, 12 просмотров)

0