26.2.. Ranije je izložen algoritam za izračunavanje prostih brojeva. U ovom algoritmu se za svaki broj provjeravalo da li je djeljiv sa nekim od brojevado polovice njegove vrijednosti.

Opis rješenja: Ranije je izložen algoritam za izračunavanje prostih brojeva. U ovom algoritmu se za svaki broj provjeravalo da li je djeljiv sa nekim od brojevado polovice njegove vrijednosti.
Algoritam zvan Eratostenovo sito se razlikuje od spomenutog. U ovom algoritmu se prvo formira sito. Na pocetku su u situ svi prirodni brojevi do N do kojeg se traže prosti brojevi. Zatim se polazi od broja 2 do polovice broja N. Za sve ove brojeve se iz sita izbacuju umnošci ovih brojeva. Na primjer za broj 2 se iz sita izbacuju brojevi 4,6, 8, ... , N/2 (t. 2*2, 2*3, 2*4, ..., N/2), jer su svi ovi brojevi djeljivi sa 2, znači nisu prosti.
Glavni program poziva pp za dimenzionisanje niza (pp 400), a zatim pp za početne vrijednosti i naslov 200. PP 100 je za izdvajanje umnoška. Svi brojevi oji su jednai umnošku nisu prosti, zato se indiator Xi postavlja na nulu.
Posavljanje početnih vrijednosti ispis naslova i učitavanje broja se izvodi u pp 200. Međutim, može se učitati samo broj zaključno sa 1000. PP 300 izvodi ispis preostalih (prostih) brojeva.
Zadnji je pp 400 koji izvodi dimenzionisanje niza.

Spisak varijabi:
N - učitan broj X ' indikator da li je broj prost (1/0)

Listing programa:

REM 26011090
1 REM ERATOSTENOVO SITO
GOSUB 400: REM dimenzionisanje niza
DIM X(1000)
30 GOSUB 200: REM naslov i pocetne vrijednosti
GOSUB 100: REM izdvajanje umnozaka
GOSUB 300: REM ispis prostih brojeva
INPUT "Hoces li jos (/N) "; DA$: REM nastavak sa novim intervalom
IF LEFT$(da$, 1) <> "N" THEN GOTO 30
END

100 REM Izdvajanje umnozaka
110 FOR i = 2 TO n / 2
    120 FOR j = i + i TO n STEP i
        130 X(j) = 0
    140 NEXT j
150 NEXT i
190 RETURN

200 REM Naslov i pocetne vrijednosti
210 CLS: PRINT TAB(10); "Eratostenovo sito "
220 PRINT: PRINT
230 INPUT "Ucitati broj (<1001) "; n
240 IF n > 1000 THEN GOTO 230
250 PRINT
260 FOR i = 1 TO n
    270 X(i) = 1
280 NEXT i
290 RETURN

300 REM Ispis preostalih brojeva u Eratostenovom situ
310 PRINT "Prosi brojeve do "; n; " su: "
330 FOR i = 1 TO n
    340 IF X(i) = 1 THEN PRINT i; ", ";
350 NEXT i
360 PRINT
390 RETURN

400 REM Dimenzionisanje niza
REM DIM X(1000)
RETURN

990 END

Ispis na ekranu:

Index