Szita Sundarama

A Sundarama szita egy determinisztikus algoritmus az összes prímszám megkeresésére néhány egész számig . Sundaram indiai diák tervezte 1934-ben. $n$

Az algoritmus kizárja a természetes számok sorozatából 1-től az összes számig az alábbi formában: $N$

i+j+2ij

ahol az indexek átfutnak minden olyan természetes értéken, amelyre vonatkozóan , nevezetesen a és értékei Ezután a fennmaradó számok mindegyikét megszorozzuk 2-vel és növeljük 1-gyel. A kapott sorozat az intervallum összes prímszáma . $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]$

Indoklás

Az algoritmus egynél nagyobb páratlan természetes számokkal működik, amelyek jelölése , ahol egy természetes szám. $2m+1$ $m$

Ha egy szám összetett , akkor definíció szerint két egynél nagyobb páratlan szám szorzataként ábrázolható, azaz: $2m+1$

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

, ahol és vannak természetes számok. A zárójeleket kibontva azt kapjuk

én

j

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

, vagy

2m=4ij+2i+2j

, amiből az következik

m=2ij+i+j

Így, ha az összes ( ) alakú számot kizárjuk a természetes számok sorozatából, akkor a fennmaradó számok mindegyikénél a számnak prímnek kell lennie. És fordítva, ha a szám prím, akkor a szám nem ábrázolható formában , és így nem lesz kizárva az algoritmus során. $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 ] = igaz ; } 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 ] = hamis ; } } for ( int i = 1 ; i <= n ; i ++ ) { if ( a [ i ]) { printf ( "%d " , 2 * i + 1 ); } } return 0 ; }

Megvalósítási példa a python3.8-ban

n = int ( bemenet ()) sc = set ( tartomány ( 1 , n + 1 )) i esetén az ( 1 , int ( ( ( 2 * n + 1 ) ** 0,5 ) - 1 ) / 2 ) + 1 ): j esetén az ( i , ( n - 1 ) tartományban // ( 2 * i ) + 1 ) + 1 ): sc . eltávolítás ( i + j + 2 * i * j ) sc = rendezve ( i * 2 + 1 i in sc ) _ nyomtatás ( sc )

Lásd még

Linkek

B. A. Kordemszkij. Matematikai okosság . — M .: GIFML, 1958.
Baxter, Andrew. Sundaram szita . Témák a kriptográfia történetéből. MU Matematika Tanszék.