Исследуем формулу Эйлера как генератор простых чисел.

Cn=n*n+n+41

Напишем код на Python и Forth для проверки количества простых чисел при n = от 0 до 100, 1000, 10000, 50000 и 65000.

Рассмотрим также C=27941 как замену 41, и сделаем вывод что многочлен с таким свободным членом генерирует больше простых чисел.

Код для подсчета количества простых чисел, генерируемое формулой Cn=n*n+n+41 (Cn=n*n+n+27941) на ЯП Forth.

S" lib\include\float2.f" INCLUDED
S" lib\include\facil.f" INCLUDED

: TIME TIME&DATE 2DROP 24 * + 60 * + 60 * + ;

: IS_PRIME ( N -> D )
    DUP 4 < IF DROP 1 EXIT THEN
    DUP 2 MOD 0= IF DROP 2 EXIT THEN
    DUP 0 D>F FSQRT F>D DROP 2 + 3 DO
        DUP I MOD 0= IF DROP I 0 LEAVE THEN
    2 +LOOP IF 1 ELSE THEN
;

: TST 20 0 DO I DUP . IS_PRIME . CR LOOP ;

: EULER ( N K -> )
    0 SWAP ROT 0 DO
        DUP I DUP 1+ * +
        IS_PRIME 1 = IF SWAP 1+ SWAP THEN
    LOOP DROP
;

: MAIN
TIME
    65000 41 EULER . \ код для проверки
TIME SWAP - CR ." ZANYALO " . ." sec" ;

MAIN

Первый параметр n, второй - C=41 или C=27941.

100 41 EULER .
86 Ok
100 27941 EULER .
77 Ok

1000 41 EULER .
581 Ok
1000 27941 EULER .
599 Ok

10000 41 EULER .
4149 Ok
10000 27941 EULER .
4466 Ok

45000 41 EULER .
15571 Ok
45000 27941 EULER .
17075 Ok

Код для работы с беззнаковыми числами на Forth.

S" lib\include\float2.f" INCLUDED
S" lib\include\facil.f" INCLUDED

: TIME TIME&DATE 2DROP 24 * + 60 * + 60 * + ;

: 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
;

: TST 20 0 DO I DUP . IS_PRIME . CR LOOP ;

: EULER ( N K -> )
    0 SWAP ROT 0 DO
        DUP I DUP 1+ * +
        IS_PRIME 1 = IF SWAP 1+ SWAP THEN
    LOOP DROP
;

: MAIN
TIME
    50000 27941 EULER . \ код для проверки
TIME SWAP - CR ." ZANYALO " . ." sec" ;

MAIN

Без измерения времени выполнения:

50000 41 EULER .
17071 Ok
50000 27941 EULER .
18776 Ok

65000 41 EULER .
21631 Ok
65000 27941 EULER .
23793 Ok

С измерением времени выполнения:

MAIN \ 50000 27941 EULER
18776
ZANYALO 1 sec Ok

MAIN \ 50000 41 EULER
17071
ZANYALO 0 sec Ok

MAIN \ 65000 27941 EULER
23793
ZANYALO 2 sec Ok

MAIN \ 65000 41 EULER
21631
ZANYALO 2 sec Ok

Только при n=100, формула Эйлера с C=41 генерирует больше простых чисел, чем с C=27941. При n = 1000, 10000, 50000 и 65000 - C=27941 "побеждает", генерирует больше простых чисел.

Forth работает только с 32 битными числами (примерно +/- 2 миллиарда). Квадратный корень из 2**31 грубо 46000 плюс значения остальных членов суммы, то есть можем спокойно прогнать n до 45000. При работе с беззнаковыми числами - квадратный корень из 2**32=65536, а это значит, что можем увеличить диапазон до 65000.

Код на Python проще и понятнее (приведен ниже, сравните сами), но выполняется примерно в 15 раз дольше. Также минусом Forth является отсутствие библиотек для работы с длинными числами.

Код для подсчета количества простых чисел, генерируемое формулой Cn=n*n+n+41 (Cn=n*n+n+27941) на ЯП Python.

import time

def is_prime(n):
    if n%2 == 0:
        return 2
    for i in range(3,int(n**0.5)+1,2):
        if n%i == 0:
            return i
    return 1

def Euler(m,k):
    start_time = time.time()
    c=0
    for i in range(m):
        n=i*(i+1)+k
        if is_prime(n)==1:
            c+=1
    end_time = time.time()
    elapsed_time = end_time - start_time
    print(f"Время выполнения: {elapsed_time:.2f} секунд")
    return c

Euler(100,41)
Время выполнения: 0.00 секунд
86
Euler(100,27941)
Время выполнения: 0.00 секунд
77

Euler(1000,41)
Время выполнения: 0.01 секунд
581
Euler(1000,27941)
Время выполнения: 0.03 секунд
599

Euler(10000,41)
Время выполнения: 0.72 секунд
4149
Euler(10000,27941)
Время выполнения: 0.78 секунд
4466

Euler(45000, 41)
Время выполнения: 15.91 секунд
15571
Euler(45000, 27941)
Время выполнения: 16.98 секунд
17075

Euler(50000, 41)
Время выполнения: 19.69 секунд
17071

Euler(50000, 27941)
Время выполнения: 21.69 секунд
18776

Euler(65000, 41)
Время выполнения: 35.07 секунд
21631

Euler(65000, 27941)
Время выполнения: 38.62 секунд
23793

Euler(100000,41)
Время выполнения: 85.23 секунд
31985
Euler(100000,27941)
Время выполнения: 93.43 секунд
35150

 

Двенадцать новых чисел для формулы Эйлера:

Для 55661 процент простых чисел 19214 / 50000 * 100% = 38.428%
Для 72491 процент простых чисел 19120 / 50000 * 100% = 38.24%

115721 19860 / 50000 * 100 % = 39,72%
136517 19392 / 50000 * 100 % = 38,784%

247757 21203 / 50000 * 100 % = 42,406%
239621 19812 / 50000 * 100 % = 39,624%
206807 19248 / 50000 * 100 % = 38,496%

333491 19576 / 50000 * 100 % = 39,152%
361637 19596 / 50000 * 100 % = 39,192%
383681 19193 / 50000 * 100 % = 38,386%

487451 19035 / 50000 * 100 % = 38,07%
460631 18727 / 50000 * 100 % = 37,454%

 

Euler(10000, 55661)
Время выполнения: 0.80 секунд
4544
Euler(50000, 55661)
Время выполнения: 22.43 секунд
19214

Euler(10000, 72491)
Время выполнения: 0.80 секунд
4533
Euler(50000, 72491)
Время выполнения: 22.15 секунд
19120

По сравнению с 41 и 27941, которые дают результаты:

17071 / 50000 * 100% = 34,142%
18776 / 50000 * 100% = 37,552%

 

Euler(10000, 115721)
Время выполнения: 0.85 секунд
4690
Euler(50000, 115721)
Время выполнения: 23.50 секунд
19860

Euler(10000, 136517)
Время выполнения: 0.83 секунд
4609
Euler(50000, 136517)
Время выполнения: 23.15 секунд
19392

Euler(10000, 247757)
Время выполнения: 0.91 секунд
5027
Euler(50000, 247757)
Время выполнения: 25.15 секунд
21203

Euler(10000, 239621)
Время выполнения: 0.86 секунд
4724
Euler(50000, 239621)
Время выполнения: 23.55 секунд
19812

Euler(10000, 206807)
Время выполнения: 0.83 секунд
4601
Euler(50000, 206807)
Время выполнения: 22.77 секунд
19248

Euler(10000, 333491)
Время выполнения: 0.85 секунд
4668
Euler(50000, 333491)
Время выполнения: 23.26 секунд
19576

Euler(10000, 361637)
Время выполнения: 0.85 секунд
4634
Euler(50000, 361637)
Время выполнения: 23.33 секунд
19596

Euler(10000, 383681)
Время выполнения: 0.84 секунд
4612
Euler(50000, 383681)
Время выполнения: 22.72 секунд
19193

Euler(10000, 487451)
Время выполнения: 0.84 секунд
4537
Euler(50000, 487451)
Время выполнения: 22.47 секунд
19035

Euler(10000, 460631)
Время выполнения: 0.81 секунд
4439
Euler(50000, 460631)
Время выполнения: 22.30 секунд
18727

Плюс еще 26 свободных членов для формулы Эйлера для генерации простых чисел:

10000 595937 EULER .
4978 Ok
50000 595937 EULER .
21081 Ok

10000 579431 EULER .
4589 Ok
50000 579431 EULER .
19288 Ok

10000 601037 EULER .
4604 Ok
50000 601037 EULER .
19341 Ok

10000 701147 EULER .
4712 Ok
50000 701147 EULER .
20013 Ok

10000 771581 EULER .
4669 Ok
50000 771581 EULER .
19520 Ok

10000 765197 EULER .
4666 Ok
50000 765197 EULER .
19787 Ok

10000 722231 EULER .
4609 Ok
50000 722231 EULER .
19539 Ok

10000 878357 EULER .
4510 Ok
50000 878357 EULER .
19133 Ok

10000 1544987 EULER .
4809 Ok
50000 1544987 EULER .
20431 Ok

10000 1974881 EULER .
4643 Ok
50000 1974881 EULER .
19932 Ok

10000 1272851 EULER .
4570 Ok
50000 1272851 EULER .
19428 Ok

10000 1840997 EULER .
4563 Ok
50000 1840997 EULER .
19388 Ok

10000 1000817 EULER .
4556 Ok
50000 1000817 EULER .
19467 Ok

10000 1257911 EULER .
4519 Ok
50000 1257911 EULER .
19169 Ok

10000 1850747 EULER .
4511 Ok
50000 1850747 EULER .
19344 Ok

10000 1426697 EULER .
4495 Ok
50000 1426697 EULER .
19234 Ok

10000 1087211 EULER .
4462 Ok
50000 1087211 EULER .
18909 Ok

10000 2640161 EULER .
4798 Ok
50000 2640161 EULER .
20568 Ok

10000 2367767 EULER .
4767 Ok
50000 2367767 EULER .
20428 Ok

10000 2603297 EULER .
4595 Ok
50000 2603297 EULER .
19605 Ok

10000 2719391 EULER .
4580 Ok
50000 2719391 EULER .
19713 Ok

10000 2094341 EULER .
4564 Ok
50000 2094341 EULER .
19397 Ok

10000 2655671 EULER .
4488 Ok
50000 2655671 EULER .
19153 Ok

10000 2039747 EULER .
4440 Ok
50000 2039747 EULER .
19027 Ok

10000 2567177 EULER .
4435 Ok
50000 2567177 EULER .
19276 Ok

10000 2960381 EULER .
4387 Ok
50000 2960381 EULER .
18881 Ok