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.
Az algoritmus kizárja a természetes számok sorozatából 1-től az összes számig az alábbi formában:
,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 .
Az algoritmus egynél nagyobb páratlan természetes számokkal működik, amelyek jelölése , ahol egy természetes szám.
Ha egy szám összetett , akkor definíció szerint két egynél nagyobb páratlan szám szorzataként ábrázolható, azaz:
, ahol és vannak természetes számok. A zárójeleket kibontva azt kapjuk , vagy , amiből az következik .Í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.
#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 )