Как сгенерировать/проверить простое число

[qwertyfuck]

Собственно вопрос: как сгенерировать случайное простое число ?
если воспользоваться генератором случайного числа то как организовать его проверку на простоту ?

[Сергей0308]

Собственно вопрос: как сгенерировать случайное простое число ?
если воспользоваться генератором случайного числа то как организовать его проверку на простоту ?

Тестов простоты немерено, глаза разбегаются, какая здесь проблема?!
https://ru.wikipedia.org/wiki/Простое_число

49631

Например такой: https://ru.wikipedia.org/wiki/Тест_Агравала_—_Каяла_—_Саксены

Для начала можно использовать самый понятный метод - метод перебора делителей(https://ru.wikipedia.org/wiki/Перебор_делителей), кстати он и самый медленный! Ограничим диапазон в пределах миллиона(у вас же ключ открытый), тогда, значение делителей будет не более 1000(квадратный корень из миллиона), в этом диапазоне имеется всего 168 делителей:

49632

Даже последовательно перебирая делители при цикле программы 3 мс это займёт полсекунды, наверно вас это устроит, если не устроит никто не запрещает это параллейно выполнить, тогда время ограничится временем цикла программы, всё!

[Mask]

Самый простой способ (как мне видится): делаем массив простых чисел, генерируем случайное число в пределах длины массива и вынимаем простое число по полученному индексу. Из минусов - потеря времени на формирование массива если это делать руками, но никто не запрещает написать утилитку, которая будет генерировать массив требуемой длины.

[Сергей0308]

Самый простой способ (как мне видится): делаем массив простых чисел, генерируем случайное число в пределах длины массива и вынимаем простое число по полученному индексу. Из минусов - потеря времени на формирование массива если это делать руками, но никто не запрещает написать утилитку, которая будет генерировать массив требуемой длины.

А в ОЛ(ПР) есть массивы?

[melky]

з.ы. вроде для ОЛ же писали генератор случайных чисел ? Если да, то число можно использовать для выемки ячейки ППЗУ, в котором как раз и указать список простых чисел.

[Сергей0308]

з.ы. вроде для ОЛ же писали генератор случайных чисел ? Если да, то число можно использовать для выемки ячейки ППЗУ, в котором как раз и указать список простых чисел.

И сколько потребуется лет чтобы записать в ПЗУ все простые числа хотя бы диапазона UDINT, что поддерживает ОЛ(ПР)?
Мне почему то кажется что более 20 лет уйдёт, если на каждое число тратить по 1-ой секунде!

[Mask]

А в ОЛ(ПР) есть массивы?

Действительно, нету, уже настолько привык что все это есть вот и написал.

[melky]

Сергей0308 а я сказал записывать ВСЕ числа ? можно сделать набор всего из 32-х числел, не применять 5, 7, 11 а просто с большим количеством цифр.
Раз это ключ, думаю будет вполне достаточно такого решения.
Можно сделать два макроса ППЗУ32 и периодически переключаясь между ними выбирать из них, например. И чтобы переключение тоже было случайным..