Τετάρτη 23 Μαρτίου 2011

O φίλος του Αρχιμήδη Ερατοσθένης και το Κόσκινο του.


Από τη Βικιπαίδεια
Το Κόσκινο του Ερατοσθένη: τα βήματα του αλγόριθμου για πρώτους αριθμούς μικρότερους από το 120 (περιλαμβάνει τη βελτιστοποίηση της εκκίνησης από τετράγωνα).
Στα μαθηματικά, το Κόσκινο του Ερατοσθένη είναι ένας απλός αλγόριθμος για την εύρεση όλων των πρώτων αριθμών μέχρι έναν συγκεκριμένο ακέραιο.[1] Σαν αλγόριθμος είναι γρήγορος για μικρούς πρώτους (κάτω από 10 εκατομμύρια).[2] Δημιουργήθηκε από τον Ερατοσθένη, μαθηματικό της Αρχαίας Ελλάδας. Αν και κανένα από τα μαθηματικά του έργα δεν έχει διασωθεί, το κόσκινο περιγράφεται και αποδίδεται στον Ερατοσθένη στην Εισαγωγή στην Αριθμητική του Νικόμαχου.[3]
 

Πίνακας περιεχομένων

Αλγόριθμος

Ένας πρώτος αριθμός είναι ένας φυσικός αριθμός που έχει ακριβώς δύο διαφορετικούς διαιρέτες: το 1 και τον εαυτό του.
Η εύρεση όλων των πρώτων αριθμών που είναι μικρότεροι ή ίσοι από έναν ακέραιο n, σύμφωνα με τη μέθοδο του Ερατοσθένη, γίνεται ως εξής:
  1. Δημιουργούμε μια λίστα από διαδοχικούς ακέραιους από το 2 μέχρι το n: (2, 3, 4, ..., n).
  2. Αρχικά, έστω ότι το p είναι ίσο με 2, τον 1ο πρώτο αριθμό.
  3. Διαγράφουμε από τη λίστα όλα τα πολλαπλάσια του p που είναι μικρότερα ή ίσα με n. (2p, 3p, 4p, κτλ)
  4. Βρίσκουμε τον 1ο αριθμό που απομένει στη λίστα μετά τον p (αυτός ο αριθμός είναι ο επόμενος πρώτος αριθμός) και αντικαθιστούμε το p με αυτόν τον αριθμό.
  5. Επαναλαμβάνουμε τα βήματα 3 και 4 μέχρι το p2 να είναι μεγαλύτερο από n.
  6. Όλοι οι αριθμοί που απομένουν στη λίστα είναι πρώτοι αριθμοί.

Παράδειγμα

Για να βρούμε όλους τους πρώτους αριθμούς που είναι μικρότεροι ή ίσοι από το 30, εργαζόμαστε ως εξής:
Αρχικά δημιουργούμε μια λίστα από τους ακέραιους από το 2 έως το 30:
2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
Διαγράφουμε τα πολλαπλάσια του 2 με αποτέλεσμα:
2  3     5     7     9    11    13    15    17    19    21    23    25    27    29
Ο 1ος αριθμός στη λίστα μετά το 2 είναι το 3 και διαγράφουμε τα πολλαπλάσια του 3 από τη λίστα με αποτέλεσμα:
2  3     5     7          11    13          17    19          23    25          29
Ο 1ος αριθμός στη λίστα μετά το 3 είναι το 5 και διαγράφουμε τα πολλαπλάσια του 5 από τη λίστα με αποτέλεσμα:
2  3     5     7          11    13          17    19          23                29
Ο 1ος αριθμός στη λίστα μετά το 5 είναι το 7 αλλά το τετράγωνο του 7 είναι 49 που είναι μεγαλύτερο από το 30, επομένως η διαδικασία τελείωσε. Η τελική λίστα αποτελείται από όλους τους πρώτους αριθμούς που είναι μικρότεροι ή ίσοι από 30.

Πολυπλοκότητα αλγορίθμου και υλοποίηση

Η διαγραφή των πολλαπλασίων κάθε πρώτου αριθμού που εντοπίζεται μπορεί να αρχίζει από το τετράγωνο κάποιου αριθμού, μιας και τα μικρότερα πολλαπλάσια έχουν ήδη διαγραφεί σε προηγούμενα βήματα.
Η πολυπλοκότητα του αλγορίθμου είναι O(n(logn)(loglogn)) λειτουργίες bit με απαιτήσεις μνήμης O(n).[4] Η χρονική πολυπλοκότητα στο μοντέλο μηχανής RAM είναι O(nloglogn) λειτουργίες, κάτι που προκύπτει κατευθείαν από το ότι οι αρμονική σειρά πρώτων (prime harmonic series) τείνει ασυμπτωτικά στο 1/(ln(ln(N))). Η κατακερματισμένη έκδοση του κόσκινου του Ερατοσθένη, με βασικές βελτιστοποιήσεις, χρησιμοποιεί O(n) λειτουργίες και O(n1 / 2loglogn / logn) bits μνήμης.[5]
Το 1975, ο Ντέιβιντ Τέρνερ (David Turner) πρότεινε ότι το κόσκινο των πρώτων αριθμών μπορεί να αναπαρασταθεί με έναν πολύ απλό και κομψό τρόπο, χρησιμοποιώντας αμιγώς συναρτησιακές γλώσσες προγραμματισμού.[6] Το κόσκινο του Τέρνερ, που μοιάζει αρκετά με το κόσκινο του Όιλερ παρακάτω, υλοποιείται σε Haskell ως εξής:
primes = sieve [2..]
 sieve (p : xs) = p : sieve [x | x <- xs, x `mod` p > 0]
Το 2008, η Μελίσα Ο'Νιλ (Melissa O'Neill) έδειξε ότι η πολυπλοκότητα του αλγορίθμου του Turner είναι σημαντικά χειρότερη από την πολυπλοκότητα των κλασικών προστακτικών εκδόσεων του κόσκινου.[7] Η Ο'Νιλ έδειξε μια έκδοση του κόσκινου του Ερατοσθένη σε Haskell με τη χρήση ουρών προτεραιότητας (priority queues) που έχει πολυπλοκότητα παρόμοια με αυτή των κλασικών προστακτικών υλοποιήσεων.

Το Κόσκινο του Όιλερ

Ο Όιλερ, στην απόδειξή του για το γινόμενο Όιλερ της ζ-συνάρτησης του Ρίμαν, χρησιμοποίησε μια έκδοση του κόσκινου του Ερατοσθένη, η οποία ήταν καλύτερη γιατί κάθε αριθμός απαλειφόταν ακριβώς μια φορά. Σε αντίθεση με το κόσκινο του Ερατοσθένη που διαγράφει πολλαπλάσια των πρώτων αριθμών που βρίσκει από την ίδια ακολουθία, το κόσκινο του Όιλερ χρησιμοποιεί ακολουθίες που έχουν δημιουργηθεί διαδοχικά από πολλαπλάσια των προηγούμενων πρώτων αριθμών:
Α) Αρχίζουμε με όλους τους φυσικούς αριθμούς εκτός από το '1' που δεν είναι πρώτος αριθμός:

  2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 ...
  ^

Β) Ο αριθμός στα αριστερά είναι πρώτος. Πολλαπλασιάζουμε κάθε αριθμό
   στη λίστα με αυτόν και αγνοούμε τα γινόμενα:

 (4 6 8 10 12 14 16 18 20 22 24 26 28 30 ... )

  Διαγράφονται:
      4   6   8   10    12    14    16    18    20    22    24    26    28    30 

  Παραμένουν:
  2 3   5   7   9    11    13    15    17    19    21    23    25    27    29 ...
    ^

Γ) Ο αριθμός πριν τον προηγούμενο πρώτο είναι επίσης πρώτος. Πολλαπλασιάζουμε με αυτόν κάθε
   αριθμό στη λίστα αρχίζοντας από αυτόν τον πρώτο και αγνοούμε τα γινόμενα:

   (9   15  21  27   33    39    45    51    57    63    69    75    81    87 ...)

  Αφαιρούνται:
                9                15                21                27 

  Παραμένουν:
  2 3   5   7        11    13          17    19          23    25          29 ...
        ^
Επαναλαμβάνουμε το Γ) επ' άπειρον. Σε κάθε επανάληψη εντοπίζουμε έναν νέο πρώτο αριθμό (που μαρκάρεται με το δείκτη , ^) μέχρι να βρεθούν όλοι οι πρώτοι στην αρχική λίστα. Πρέπει να σημειωθεί ότι οι αριθμοί που απορρίπτονται εξακολουθούν να χρησιμοποιούνται για την κατασκευή του τρέχοντος κόσκινου, δηλ. όταν κατασκευάζουμε ένα κόσκινο για το 3 κάνουμε τις πράξεις 3*3=9, 3*5=15, 3*7=21, ... 3*15=45, ... Το 15 που απορρίπτεται χρησιμοποιείται για την κατασκευή του κόσκινου και μετά οι αριθμοί αφαιρούνται από τη λίστα.
Το κόσκινο του Όιλερ είναι μια καλή λύση για την παραγωγή άπειρων ακολουθιών πρώτων αριθμών και το κόσκινο του Τέρνερ είναι μια κοντινή εκδοχή του.
Σε Haskell γράφεται:
import Data.OrdList (minus)
 
 primes = euler [2..]
 euler (p : xs) = p : euler (xs `minus` map (*p) (p : xs))
Σε Python:
def euler_sieve(n):
    # δημιουργεί έναν πίνακα από περιττούς αριθμούς.
    num_tab = range(1,n,2)
    # ο πίνακας είναι ο 1,3,5,7,... αλλάζουμε το 1ο στοιχείο
    # στον πρώτο αριθμό, 2
    num_tab[0] = 2
    i = 1
    # ο μεγαλύτερος αριθμός στον πίνακα
    highestval = num_tab[-1]
    while True:
        # βρες τον 1ο τελεστή στο κόσκινο
        cx = num_tab[i]
        # αν τιμή που δε δουλεύει, προχώρησε στην επόμενη
        if cx == False:
            i += 1
            continue
        # η 1η τιμή που περνάει από το κόσκινο είναι πάντα ο
        # τρέχων αριθμός * τον εαυτό του. όλοι οι άλλοι αριθμοί
        # στο κόσκινο θα είναι μεγαλύτεροι.
        if cx**2 > n:
            break
        # διαγράφει - κόσκινο
        tostrike = []
        for j in xrange(i,len(num_tab)):
            # βρίσκει τον 2ο τελεστή στο κόσκινο
            cy = num_tab[j]
            # αν τιμή που δε δουλεύει, αγνόησε τα υπόλοιπα
            if cy == False:
                continue
            cut = cx*cy
            # εκτός των ορίων του κόσκινου
            if cut > highestval:
                break
            # προσθέτει στο κόσκινο
            tostrike.append(cut)
        # περνάει από το κόσκινο τις τιμές από τον πίνακα των αριθμών μας
        for d in tostrike:
            ind = (d - 1)/2
            num_tab[ind] = False
        # βρίσκει τη μεγαλύτερη τιμή στον πίνακα που δεν
        # έχει περάσει από το κόσκινο
        hiind = -1
        while num_tab[hiind] == False:
            hiind -= 1
        highestval = num_tab[hiind]
 
        i += 1
    return num_tab
 
...
 
    print [x for x in euler_sieve(100) if x != False]
Στον αλγόριθμο αυτό, σε σύγκριση με τον αλγόριθμο που χρησιμοποιεί ο Όιλερ στην απόδειξή του, οι πρώτοι αριθμοί αριστερά του δείκτη αντιστοιχούν σε παράγοντες του αριστερού μέλους της εξίσωσης σε κάθε στάδιο του κόσκινου, ενώ η ακολουθία στα δεξιά, μαζί με τη θέση του δείκτη, αντιστοιχεί στη σειρά του δεξιού μέλους της εξίσωσης σε κάθε στάδιο (εκτός από το αρχικό).
Όταν παράγουμε μια πεπερασμένη λίστα πρώτων, όταν ξεπεράσουμε το τετράγωνο του άνω ορίου του εύρους μας, έχουμε την επιθυμητή ακολουθία πρώτων αριθμών. Στο παραπάνω παράδειγμα, αυτό συμβαίνει όταν εντοπίζουμε τον πρώτο αριθμό 7, για να βρούμε τη λίστα όλων των πρώτων αριθμών μέχρι το 30.

Δείτε επίσης

Παραπομπές

  1. ↑ Horsley, Rev. Samuel, F. R. S., "Κόσκινον Ερατοσθένους or, The Sieve of Eratosthenes. Being an Account of His Method of Finding All the Prime Numbers," Philosophical Transactions (1683-1775), Vol. 62. (1772), pp. 327-347.
  2. ↑ The Prime Glossary: "The Sieve of Eratosthenes", http://primes.utm.edu/glossary/page.php?sort=SieveOfEratosthenes, references 16. November 2008.
  3. ↑ Νικόμαχος, Εισαγωγή στην Αριθμητική, I, 13. [1]
  4. ↑ Pritchard, Paul, "Linear prime-number sieves: a family tree," Sci. Comput. Programming 9:1 (1987), pp. 17–35.
  5. ↑ A. O. L. Atkin and D. J. Bernstein, "Prime sieves using binary quadratic forms", Mathematics of Computation 73 (2004), pp. 1023–1030.
  6. ↑ Turner, David A. SASL language manual. Tech. rept. CS/75/1. Department of Computational Science, University of St. Andrews 1975.
  7. ↑ O'Neill, Melissa E., "The Genuine Sieve of Eratosthenes", Journal of Functional Programming, Published online by Cambridge University Press 09 Oct 2008 doi:10.1017/S0956796808007004.

Εξωτερικοί σύνδεσμοι

Wikipedia-logo.png Στο άρθρο αυτό έχει ενσωματωθεί κείμενο από το άρθρο Sieve of Eratosthenes της Αγγλόγλωσσης Βικιπαίδειας, η οποία διανέμεται υπό την GNU FDL και την CC-BY-SA 3.0. (ιστορικό/συντάκτες).
Αναρτήθηκε από στις
Ετικέτες , ,

Δεν υπάρχουν σχόλια:

Δημοσίευση σχολίου

Εγγραφή σε: Σχόλια ανάρτησης (Atom)