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

Содержание

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

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

Таблицы 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