SBC6502 - 61 - basic programs - Eratosthenovo sito. Sieve of Eratosthenes.

By Administrator at January 12, 2023 13:06
Filed Under: SBC6502

Ďalší zo zaujímavých programov v jazyku Basic pre 8-bity. Eratosthenovo sito je algoritmus pre nájdenie všetkých prvočísel menších ako zadaná horná hranica. Algoritmus je pomenovaný po gréckom matematikovi Eratosthenovi, ktorý žil v rokoch 276–194 pred Kr.

Algoritmus funguje na postupnom „presievaní“ zoznamu čísel – na začiatku zoznam obsahuje všetky čísla v danom rozsahu (2, 3, 4, …, zadané maximum). Potom sa opakovane prvé číslo zo zoznamu vyberie, toto číslo je prvočíslom; zo zoznamu sa potom odstránia všetky násobky tohto čísla (to sú zložené čísla). Tak sa pokračuje až dovtedy, kým sa zo zoznamu neodstráni posledné číslo (alebo dovtedy, keď je ako prvočíslo označené číslo vyššie ako odmocnina najvyššieho čísla – v tomto prípade všetky zostávajúce čísla v zozname sú určite prvočísla).

 

Obrázok pochádza z Wikimedia Commons.

Tento súbor /obrázok/ podlieha licencii:

Creative Commons Attribution-Share Alike 3.0 Unported


Príklad pre nájdenie prvočísel medzi prvými 20 číslami :

Krok 1: Zoznam obsahuje všetky čísla v rozsahu 2–20:

    Zoznam: 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

Krok 2: Odoberieme prvé číslo zo zoznamu a označíme ho ako prvočíslo:

    Známe prvočísla: 2
    Zoznam: 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

Krok 3: Odoberieme zo zoznamu všetky násobky práve odobratého prvočísla:

    Známe prvočísla: 2
    Zoznam: 3 5 7 9 11 13 15 17 19

Krok 4: Pokračujeme opäť bodom 2, pokiaľ ostávajú nejaké čísla :

    Známe prvočísla: 2 3
    Zoznam: 5 7 11 13 17 19

    Známe prvočísla: 2 3 5
    Zoznam: 7 11 13 17 19

    5 je vyšší než ?19, takže ostávajú už iba prvočísla.

Výsledný zoznam prvočísel v rozsahu 2–20: 2, 3, 5, 7, 11, 13, 17, 19.


Základné informácie sú prevzaté z: 

https://sk.wikipedia.org/wiki/Eratostenovo_sito

___________________________________________________________


Vlastný program:

je prevzatý a iba mierne upravený pre možnosti SBC6502 /maximum je S=89 namiesto S=100, je k dispozícii príliš malá RAM/ zo stránky:

https://www.xenesis.jp/2022/05/sieve-fp-basic/


 100 S=89
 110 M=S*S
 120 DIM P(M)
 130 ? "INIT TABLE"
 140 FOR I=2 TO M
 150 P(I)=1
 160 NEXT I
 170 ? "SIEVE CALC"
 180 FOR I=2 TO S
 190 IF P(I) <> 1 THEN GOTO 240
 200 ? I; ",";
 210 FOR J=I TO M/I
 220 P(I*J)=0
 230 NEXT J
 240 NEXT I
 244 ?
 250 ?
 260 ? "PRIME NUMBERS"
 270 FOR I=2 TO M
 280 IF P(I)=1 THEN ? I; ",";
 290 NEXT I

 

Download programu:

Erastothenes1.txt (358,00 bytes)

 

nasleduje skrátená verzia uvedeného programu, tu sú už riadky "zrazené" k sebe:


 100 S=89:M=S*S:DIM P(M):? "INIT TABLE"
 140 FOR I=2 TO M:P(I)=1:NEXT I:? "SIEVE CALC"
 180 FOR I=2 TO S:IF P(I) <> 1 THEN GOTO 240
 200 ? I; ",";:FOR J=I TO M/I:P(I*J)=0:NEXT J
 240 NEXT I:?:?:? "PRIME NUMBERS"
 270 FOR I=2 TO M:IF P(I)=1 THEN ? I; ",";

 290 NEXT I

 

Download programu:

Erastothenes2.txt (274,00 bytes)

 

Prvá časť výpisu v terminálovom okne, pokračuje až po ...


číslo 7919 ...

 

Program je naozajstným "žrútom" dostupnej RAM:

Max. možné je použiť číslo S=89 v riadku č.100, pri 32kB RAM SBC6502 potom zostáva už iba 254 voľných byte RAM.

Asi je dobré popísať metodiku merania času:

Doba výpočtu na SBC6502 (x-tal = 4.9152MHz), meria sa po zobrazení čísla 89 na displeji = 23.4sec

/v časti SIEVE CALC, nazvem to medzičasom/

Ak zarátame ďalší výpis čísiel od PRIME NUMBERS po 7919, tak celkový čas behu programu = 32sec


/Tu by sa hodilo mať RAM v SBC6502 rozšírenú na väčšiu hodnotu  - 40kB alebo 46kB RAM ..., po programe pre kontrolu checksum OS je to asi len  druhý prípad kedy to konštatujem./

Poznámka:
V prípade skráteného zápisu pri použití S=89 zostáva voľných 302 byte RAM, doba výpočtu sa skráti o cca 0.7sec.

_____________________________________________________________

Vaše hodnotenie, Rate post:

Comments

1/12/2023 1:09:47 PM #

trackback

Directory SBC6502

Directory SBC6502

Igi blog |

Info o autorovi

Volám sa Igor Gramblička, bydlisko: Bratislava, Slovakia. Môj nick: Igi. Blog je o mojich záujmoch, predtým som pracoval ako IT špecialista na počítačové siete a redakčné systémy pre viaceré denníky - až som pred rokmi nakoniec v jednom z nich zakotvil a kde som to potiahol až do konca mojej profesnej kariéry.

Rok, mesiac, počet článkov: