Seula Sundarama

Sundarama-seula on deterministinen algoritmi kaikkien alkulukujen löytämiseksi johonkin kokonaislukuun asti . Sen on suunnitellut intialainen opiskelija Sundaram vuonna 1934. $n$

Algoritmi sulkee pois luonnollisten lukujen sarjasta 1:stä kaikkiin muodon lukuihin: $N$

i+j+2ij

jossa indeksit kulkevat kaikkien luonnollisten arvojen läpi , eli arvot ja Sitten jokainen jäljellä olevista luvuista kerrotaan kahdella ja lisätään 1:llä. Tuloksena oleva sarja on kaikki välin alkuluvut . $i\leqslant j$ $i+j+2ij\leqslant N$ $i=1,\;2,\;\ldots ,\;\left\lfloor {\frac ({\sqrt {2N+1}}-1}2}\right\rfloor$ $j=i,\;i+1,\;\ldots ,\;\left\lfloor {\frac {Ni}{2i+1}}\right\rfloor .$ $[1,2N+1]$

Perustelut

Algoritmi toimii parittomilla luonnollisilla luvuilla , jotka ovat suurempia kuin yksi, ja ne esitetään muodossa , jossa on luonnollinen luku. $2m+1$ $m$

Jos luku on yhdistelmä , se voidaan määritelmän mukaan esittää kahden parittoman luvun tulona, joka on suurempi kuin yksi, eli: $2m+1$

2m+1=(2i+1)(2j+1)

, missä ja ovat luonnollisia lukuja. Laajentamalla sulkuja, saamme sen

i

j

2m+1=4ij+2i+2j+1

, tai

2m=4ij+2i+2j

, josta se seuraa

m = 2ij+i+j

Jos siis kaikki muodon ( ) luvut jätetään luonnollisten lukujen sarjan ulkopuolelle, jokaisen jäljellä olevan luvun on oltava alkuluku. Ja päinvastoin, jos luku on alkuluku, niin lukua ei voida esittää muodossa , eikä sitä siten suljeta pois algoritmin aikana. $2ij+i+j$ $1\leqslant i\leqslant j$ $m$ $2m+1$ $2m+1$ $m$ $2ij+i+j$ $m$

#include <stdio.h> int main () { int n ; scanf ( "%d" , & n ); bool a [ n + 1 ]; for ( int i = 1 ; i <= n ; i ++ ) { a [ i ] = tosi ; } for ( int i = 1 ; 2 * i * ( i + 1 ) < n ; i ++ ) { int j_max = ( n - 1 ) / ( 2 * i + 1 ); for ( int j = i ; j <= j_max ; j ++ ) { a [ 2 * i * j + i + j ] = epätosi ; } } for ( int i = 1 ; i <= n ; i ++ ) { if ( a [ i ]) { printf ( "%d" , 2 * i + 1 ); } } paluu 0 ; }

Toteutusesimerkki python3.8:ssa

n = int ( syöttö ()) sc = asetettu ( alue ( 1 , n + 1 )) i :lle alueella ( 1 , int ( ((( 2 * n + 1 ) ** 0.5 ) - 1 ) / 2 ) + 1 ): j : lle alueella ( i , ( n - 1 ) // ( 2 * i ) + 1 ) + 1 ): sc . poista ( i + j + 2 * i * j ) sc = lajiteltu ( i * 2 + 1 i in sc ) _ tulostaa ( sc )

Katso myös

Linkit

B. A. Kordemsky. Matemaattinen viisaus . - M .: GIFML, 1958.
Baxter, Andrew. Sundaramin seula . Aiheita kryptografian historiasta. MU:n matematiikan laitos.