Генератор Простых чисел – формула Эйлера

Содержание

Генератор Простых чисел – формула Эйлера

Как проверить данные таблицы?

Таблицы 3-9

Проверка генератора простых чисел

Построим графики

Дополнительно

Генератор Простых чисел – формула Эйлера

Известно, что формула Эйлера – «x^2 + x + 41» дает 40 простых чисел, при x = 0 .. 39. То есть числа:

Таблица 1

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

Далее приведены таблицы чисел. В каждой по три группы из трех колонок, всего 9 колонок. Первая колонка – числа, которые следует подставить вместо «41» в исходной формуле Эйлера. Вторая колонка количество простых чисел генерируемые формулой, при выбранном свободном члене, если x перебрать от 1 до 9 999. А третья – процентное представление предыдущей колонки.

Таблица 2

Например, возьмем число «1 544 987». Формула Эйлера примет вид: «x^2 + x + 1544987». А следовательно, данная таблица утверждает, что если перебрать x от 1 до 9999, то получим, 4809 из 9999 – простых чисела. В третьей колонке «0,4809 = 4809/10 000» (для наглядности вместо 9999 выбрано – 10 000) процент простых чисел. Всего в Таблице 2 – 120 (3*40) чисел, которые генерируют простые числа с не менее чем 43% вероятностью в выбранном диапазоне для «x». Таблица упорячдочена по проценту генерируемых простых чисел (по убыванию).

Как проверить данные таблицы?

Используем Язык программирования Forth. Напишем небольшое слово на нем:

: IS_PRIME ( N -> D )

DUP 4 U< IF DROP 1 EXIT THEN

DUP 2 UMOD 0= IF DROP 2 EXIT THEN

DUP 0 D>F FSQRT F>D DROP 2 + 3 DO

 DUP I UMOD 0= IF DROP I 0 LEAVE THEN

2 +LOOP IF 1 ELSE THEN

Конец ознакомительного фрагмента.

Текст предоставлен ООО «Литрес».

Прочитайте эту книгу целиком, купив полную легальную версию на Литрес.

Безопасно оплатить книгу можно банковской картой Visa, MasterCard, Maestro, со счета мобильного телефона, с платежного терминала, в салоне МТС или Связной, через PayPal, WebMoney, Яндекс.Деньги, QIWI Кошелек, бонусными картами или другим удобным Вам способом.