Sikt Sundarama

Sundarama-sikten  är en deterministisk algoritm för att hitta alla primtal upp till något heltal . Designad av den indiska studenten Sundaram 1934.

Algoritmen möjliggör uteslutning från en serie naturliga tal från 1 till alla tal i formen:

,

där indexen går igenom alla naturvärden för vilka , nämligen värdena för och Sedan multipliceras vart och ett av de återstående talen med 2 och ökas med 1. Den resulterande sekvensen är alla primtal i intervallet .

Motivering

Algoritmen fungerar med udda naturliga tal större än ett, representerade som , där är ett naturligt tal.

Om ett tal är sammansatt kan det per definition representeras som en produkt av två udda tal större än ett, det vill säga:

, där och  är naturliga tal. Att utöka parenteserna, det förstår vi , eller , varav det följer att .

Således, om alla tal i formen ( ) exkluderas från serien av naturliga tal, måste talet för vart och ett av de återstående talen vara primtal. Och omvänt, om talet är primtal, kan talet inte representeras i formen och kommer därför inte att exkluderas under algoritmens gång.

#include <stdio.h> int main () { int n ; scanf ( "%d" , & n ); bool a [ n + 1 ]; for ( int i = 1 ; i <= n ; i ++ ) { a [ i ] = sant ; } för ( int i = 1 ; 2 * i * ( i + 1 ) < n ; i ++ ) { int j_max = ( n - 1 ) / ( 2 * i + 1 ); för ( int j = i ; j <= j_max ; j ++ ) { a [ 2 * i * j + i + j ] = falskt ; } } for ( int i = 1 ; i <= n ; i ++ ) { if ( a [ i ]) { printf ( "%d" , 2 * i + 1 ); } } returnera 0 ; }

Implementeringsexempel i python3.8

n = int ( ingång ()) sc = set ( område ( 1 , n + 1 )) för i i intervallet ( 1 , int (((( 2 * n + 1 ) ** 0,5 ) - 1 ) / 2 ) + 1 ): för j i intervallet ( i , ( n - 1 ) // ( 2 * i ) + 1 ) + 1 ): fm . ta bort ( i + j + 2 * i * j ) sc = sorterad ( i * 2 + 1 för i i fm ) print ( sc )

Se även

Länkar