  |
|
| ° Forum ° Rejestracja ° Szukaj ° | |
| Auto giełda ° wnętrzowe stacje transformatowe |
 |
Matma / Liczby Eratostenesa |
| Autor | Wiadomość |
| Posted: 4 Kwi 2001 04:14:54 -- Wiele razy pisalem sobie od reki program na sito Eratostenesa. Przy tym go lekko ulepszalem, przyspieszajac dwukrotnie i redukujac dwukrotnie pamiec. Wytlumacze na przykladzie: 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 33 35 37 39 41 43 45 47 Zachowujemy pierwsza nieskresklona/ liczbne, 3, i wykreslamy co trzecia ("check" po angielsku, czyli odfajkowac -- ja zamiast odfajkowac, skresle): 3 5 7 * 11 13 * 17 19 * 23 25 * 29 31 * 35 37 * 41 43 * 47 Nastepna liczba, ktora sie ostala jest 5, wiec ja/ zostawiamy i wykreslamy co piata/ (niektore zostana/ skreslone drugi raz; w celu skreslania skreslone traktujemy na rowni z nieskreslonyymi): 3 5 7 * 11 13 * 17 19 * 23 * * 29 31 * * 37 * 41 43 * 47 I juz mamy wszystkie liczby pierwsze mniejsze od kwadratu nastepnej nieskreslonej liczby, czyli mniejsze od 7^2 = 49. Uwaga: Komputer gdy "wykresla", a raczej odfajkowuje liczby zlozone, to wcale nie musi znac ich wartosci. wylicza je dopiero na koniec. Wczesniej poznaje tylko wartosci kolejnych pierwszych liczb nieodfajkowanych, by odfajkowac ich wielokrotnosci. To samo zachodzi w wypadku ponizszych wariantow sita Eratostenesa. --- Stosujmy sito Eratostenesa do dowolnych postepow arytmetycznych. Liczby, ktore sie ostana nazywam liczbami Eratostenesa danego postepu arytmetycznego. W wypadku postepu 6*n-1 liczby Eratostenesa, to po prostu liczby pierwsze postaci 6*n-1. Otrzymujemy je jakby nieco szybciej niz wszystkie, naprawde nieco szybciej, nie tylko pozornie: 5 11 17 23 29 35 41 47 53 59 65 71 77 83 89 95 101 107 113 119 125 131 137 143 149 155 161 167 173 179 185 191 197 203 209 215 221 227 233 239 245 251 257 263 269 275 281 287 Wykreslamy co piata/: 5 11 17 23 29 * 41 47 53 59 * 71 77 83 89 * 101 107 113 119 * 131 137 143 149 * 161 167 173 179 * 191 197 203 209 * 221 227 233 239 * 251 257 263 269 * 281 287 Zostawiamy 11 i odtad wykreslamy co 11: 5 11 17 23 29 * 41 47 53 59 * 71 * 83 89 * 101 107 113 119 * 131 137 * 149 * 161 167 173 179 * 191 197 203 * * 221 227 233 239 * 251 257 263 269 * 281 287 Ostaly sie wszystkie liczby pierwsze postaci 6*n-1, ktore sa mniejsze od 17^2 = 289. --- W wypadku postepu 6*n+1 jest ciekawiej (moze szkoda, ze ciekawiej? :-). Pozostaja liczby nie tylko pierwsze, ale pewne inne, ktore uczestnicy szanownej listy z przyjemnoscia sami odnotuja. Maja one bardzo prosta strukture, blisko zwiazana/ z tematem. W sumie, gdyby nie jednorazowy klopot z programowaniem, to nawet chyba oplacaloby sie programowac dwa sita na 6*n-1 i 6*n+1 w tej kolejnosci). Zyskuje sie pamiec, zyskuje sie troche na szybkosci nawet w porownaniu z sitem na 2*n+1. Jednak skorka nie warta wyprawki. To tyle na dzis o liczbach Eratostenesa. Nie musza byc pierwsze, za to jest ciekawiej. Pozdrawiam, Wlodek |