случайным образом 512-битное целое число N, не кратное 2, 3 или 5

Question

если вы выбираете случайное 512-битное целое число N, которое не кратно 2, 3 или 5я не знаю алгоритм, стоящий за этим ... я пытаюсь работать над проектом, но это отправная точка ..:)

Answer 1

Число простых чисел меньше n = 2 ⁵¹² составляет приблизительно n / log (n). Число рассматриваемых вами чисел равно 4/15 * n, поэтому вероятность, которую вы ищете, равна 15 / (4 * log (n)), что составляет около 1%.

Answer 2

Границы вероятности

Вы можете использовать следующее неравенство для функции простого числа :

(Где берется журнал в базе e )

Итак:

8,58774 * 10 ¹⁵¹ <& pi; (2 <sup>512 ) <8,93096 * 10 <sup>151

И поскольку вы оставляете в живых только 4/15 n чисел (из-за убийства он умножается на 2, 3 и 5), вероятность ограничена:

8,58774 * 10 ¹⁵¹ / (4/15 2 ⁵¹² )

151 / (4/15 2 ⁵¹² )

Или:

0,010507 Какая хорошая, довольно тесная связь.

Answer 3

Это звучит по-домашнему, поэтому я предлагаю вам сгенерировать 512-битные числа и использовать некоторые хорошо известные простые тесты для получения приблизительного ответа в эвристическом порядке.

Answer 4

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