Κόσκινο του Ερατοσθένη στο Python & C++

Τι είναι το κόσκινο του Ερατοσθένη;

Το Κόσκινο του Ερατοσθένη είναι το απλούστερο κόσκινο πρώτων αριθμών. Είναι ένας αλγόριθμος πρώτων αριθμών που χρησιμοποιείται για την ανακάλυψη κάθε πρώτου αριθμού εντός ενός δεδομένου ορίου. Υπάρχουν πολλά πρώτα κόσκινα, συμπεριλαμβανομένου του Κοσκίνου του Ερατοσθένη, του Κοσκίνου του Άτκιν και του Κοσκίνου του Σουνταράμ.

Η λέξη "κόσκινο«αναφέρεται σε ένα σκεύος που φιλτράρει ουσίες. Στο ίδιο πνεύμα, ο αλγόριθμος κοσκινίσματος στο Python και άλλες γλώσσες αναφέρεται σε μια μέθοδο που φιλτράρει τους πρώτους αριθμούς από μια λίστα ακεραίων.

Αυτός ο αλγόριθμος φιλτράρει τους πρώτους αριθμούς χρησιμοποιώντας μια επαναληπτική προσέγγιση. Η διαδικασία φιλτραρίσματος ξεκινά με τον μικρότερο πρώτο αριθμό. Ένας πρώτος αριθμός είναι ένας φυσικός αριθμός μεγαλύτερος από το 1 που έχει μόνο δύο διαιρέτες, δηλαδή το 1 και τον ίδιο τον αριθμό. Numbers που δεν είναι πρώτοι ονομάζονται σύνθετοι αριθμοί.

Γιατί να χρησιμοποιήσω το κόσκινο του Ερατοσθένη;

Στη μέθοδο του κόσκινου του Ερατοσθένη, επιλέγεται πρώτα ένας μικρός πρώτος αριθμός και όλα τα πολλαπλάσια του φιλτράρονται. Η διαδικασία εκτελείται σε έναν βρόχο σε ένα δεδομένο εύρος, παράγοντας αποτελεσματικά κάθε πρώτο αριθμό έως το n χωρίς να εκτελείται δοκιμαστική διαίρεση σε κάθε υποψήφιο.

Αυτό κάνει το κόσκινο πιο γρήγορο από τον έλεγχο της πρωτογένειας, έναν αριθμό τη φορά. Χρησιμοποιείται ευρέως στη θεωρία αριθμών, την κρυπτογραφία, τον κατακερματισμό και τον ανταγωνιστικό προγραμματισμό, όπου πολλοί πρώτοι αριθμοί πρέπει να δημιουργηθούν γρήγορα.

Για παράδειγμα:

Ας πάρουμε το εύρος αριθμών από το 2 έως το 10.

Αφού εφαρμόσει το κόσκινο του Ερατοσθένη, θα παράγει τη λίστα των πρώτων αριθμών 2, 3, 5, 7.

Αλγόριθμος Κόσκινο του Ερατοσθένη

Εδώ είναι ο αλγόριθμος για το κόσκινο του Ερατοσθένη:

Βήμα 1) Δημιουργήστε μια λίστα αριθμών από το 2 έως το δοσμένο εύρος n. Ξεκινάμε με το 2 επειδή είναι ο μικρότερος και πρώτος πρώτος αριθμός.

Βήμα 2) Επιλέξτε τον μικρότερο αριθμό στη λίστα, x (αρχικά το x ισούται με 2), διασχίστε τη λίστα και φιλτράρετε τους αντίστοιχους σύνθετους αριθμούς επισημαίνοντας όλα τα πολλαπλάσια του επιλεγμένου αριθμού.

Βήμα 3) Στη συνέχεια, επιλέξτε τον επόμενο πρώτο ή τον μικρότερο μη επισημασμένο αριθμό στη λίστα και επαναλάβετε το βήμα 2.

Βήμα 4) Επαναλάβετε το προηγούμενο βήμα μέχρι η τιμή του x να γίνει μικρότερη ή ίση με την τετραγωνική ρίζα του n (x<=).

Σημείωση: Η μαθηματική συλλογιστική είναι αρκετά απλή. Το εύρος αριθμών n μπορεί να παραγοντοποιηθεί ως εξής:

n = a * b

Και πάλι, n = *

= (συντελεστής μικρότερος από ) * (συντελεστής μεγαλύτερος από )

Έτσι τουλάχιστον ένα από τα πρωταρχικοί παράγοντες ή και τα δύο πρέπει να είναι <= Επομένως, διασχίζοντας μέχρι θα είναι αρκετό.

Βήμα 5) Μετά από αυτά τα τέσσερα βήματα, οι υπόλοιποι μη σημειωμένοι αριθμοί θα είναι όλοι οι πρώτοι αριθμοί σε αυτό το δεδομένο εύρος n.

Παράδειγμα με βάση την εργασία

Παράδειγμα:

Ας πάρουμε ένα παράδειγμα και ας δούμε πώς λειτουργεί.

Για αυτό το παράδειγμα, θα βρούμε τη λίστα των πρώτων αριθμών από το 2 έως το 25. Έτσι, n = 25.

Βήμα 1) Στο πρώτο βήμα, θα πάρουμε μια λίστα αριθμών από το 2 έως το 25, αφού επιλέξαμε n = 25.

Βήμα 2) Στη συνέχεια, επιλέγουμε τον μικρότερο αριθμό στη λίστα, x. Αρχικά x = 2 επειδή είναι ο μικρότερος πρώτος αριθμός. Στη συνέχεια, διασχίζουμε τη λίστα και σημειώνουμε τα πολλαπλάσια του 2.

Τα πολλαπλάσια του 2 για τη δεδομένη τιμή του n είναι: 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24.

Σημείωση: Το μπλε χρώμα υποδηλώνει τον επιλεγμένο αριθμό και το ροζ χρώμα υποδηλώνει τα πολλαπλάσια που έχουν αποκλειστεί.

Βήμα 3) Έπειτα επιλέγουμε τον επόμενο μικρότερο αμαρκάριστο αριθμό, που είναι το 3, και επαναλαμβάνουμε το τελευταίο βήμα σημειώνοντας τα πολλαπλάσια του 3.

Βήμα 4) Επαναλαμβάνουμε το βήμα 3 με τον ίδιο τρόπο μέχρι να x = ή 5.

Βήμα 5) Οι υπόλοιποι μη σημειωμένοι αριθμοί είναι οι πρώτοι αριθμοί από το 2 έως το 25.

Ψευδής-Code

Ο ακόλουθος ψευδοκώδικας αποτυπώνει τη βασική δομή του Κοσκίνου του Ερατοσθένη πριν τη μεταφράσουμε σε πραγματικό κώδικα.

Begin
	Declare a boolean array of size n and initialize it to true
	For all numbers i : from 2 to sqrt(n)
     		IF bool value of i is true THEN
         			i is prime
         			For all multiples of i (i<n)
             			mark multiples of i as composite
Print all unmarked numbers
End

Κόσκινο Ερατοσθένη Γ/C++ Code Παράδειγμα

Παρακάτω είναι ένα πλήρες C++ υλοποίηση του κόσκινου του Ερατοσθένη που τυπώνει κάθε πρώτο αριθμό μέχρι ένα επιλεγμένο άνω όριο.

#include <iostream>
#include <cstring>
using namespace std;
void Sieve_Of_Eratosthenes(int n)
{
    // Create and initialize a boolean array
    bool primeNumber[n + 1];
    memset(primeNumber, true, sizeof(primeNumber));
    for (int j = 2; j * j <= n; j++) {
        if (primeNumber[j] == true) {
            // Update all multiples of i as false
            for (int k = j * j; k <= n; k += j)
                primeNumber[k] = false;
        }
    }
    for (int i = 2; i <= n; i++)
        if (primeNumber[i])
            cout << i << " ";
}
int main()
{
    int n = 25;
    Sieve_Of_Eratosthenes(n);
    return 0;
}

Παραγωγή:

2 3 5 7 11 13 17 19 23

Κόσκινο του Ερατοσθένη Python Παράδειγμα προγράμματος

Ο ακόλουθος Python Το πρόγραμμα υλοποιεί τον ίδιο αλγόριθμο χρησιμοποιώντας μια boolean λίστα και έναν βρόχο while.

def SieveOfEratosthenes(n):
# Create a boolean array
	primeNumber = [True for i in range(n+2)]
	i = 2
	while (i * i <= n):
		if (primeNumber[i] == True):
			# Update all multiples of i as false
			for j in range(i * i, n+1, i):
				primeNumber[j] = False
		i += 1
	for i in range(2, n):
		if primeNumber[i]:
			print(i)
n = 25
SieveOfEratosthenes(n)

Παραγωγή:

2
3
5
7
11
13
17
19
23

Τμηματοποιημένο κόσκινο

Έχουμε δει ότι το Κόσκινο του Ερατοσθένη εκτελεί έναν βρόχο σε ολόκληρο το εύρος αριθμών. Επομένως, χρειάζεται χώρο μνήμης O(n) για να αποθηκεύσει τους αριθμούς. Η κατάσταση περιπλέκεται όταν προσπαθούμε να βρούμε πρώτους αριθμούς σε ένα τεράστιο εύρος, επειδή δεν είναι εφικτό να διαθέσουμε ένα τόσο μεγάλο μπλοκ μνήμης για ένα μεγαλύτερο n.

Ο αλγόριθμος μπορεί να βελτιστοποιηθεί με την εισαγωγή ορισμένων νέων χαρακτηριστικών. Η ιδέα είναι να διαιρέσουμε το εύρος αριθμών σε μικρότερα τμήματα και να υπολογίσουμε τους πρώτους αριθμούς σε αυτά τα τμήματα έναν προς έναν. Αυτός είναι ένας αποτελεσματικός τρόπος μείωσης της πολυπλοκότητας του χώρου. Αυτή η μέθοδος ονομάζεται α τμηματοποιημένο κόσκινο.

Η βελτιστοποίηση μπορεί να επιτευχθεί με τον ακόλουθο τρόπο:

1. Χρησιμοποιήστε ένα απλό κόσκινο για να βρείτε πρώτους αριθμούς από το 2 έως και αποθηκεύστε τα σε μια συστοιχία.
2. Διαιρέστε το εύρος [0…n-1] σε πολλαπλά τμήματα μεγέθους το πολύ .
3. Για κάθε τμήμα, επαναλάβετε το τμήμα και σημειώστε τα πολλαπλάσια των πρώτων αριθμών που βρέθηκαν στο βήμα 1. Αυτό το βήμα απαιτεί O() στο μέγιστο.

Το κανονικό κόσκινο απαιτεί βοηθητικό χώρο μνήμης O(n), ενώ το τμηματοποιημένο κόσκινο απαιτεί O(), η οποία αποτελεί σημαντική βελτίωση για ένα μεγάλο n. Η μέθοδος έχει επίσης ένα μειονέκτημα, επειδή δεν βελτιώνει την χρονική πολυπλοκότητα.

Ανάλυση πολυπλοκότητας

Η κατανόηση της χωρικής και χρονικής πολυπλοκότητας σάς βοηθά να επιλέξετε μεταξύ του κανονικού κόσκινου και του τμηματοποιημένου κόσκινου για ένα δεδομένο μέγεθος προβλήματος.

Διαστημική πολυπλοκότητα:

Ο απλός αλγόριθμος του κόσκινου του Ερατοσθένη απαιτεί χώρο μνήμης O(n). Το τμηματοποιημένο κόσκινο απαιτεί O() βοηθητικός χώρος.

Χρόνος πολυπλοκότητας:

Η χρονική πολυπλοκότητα ενός κανονικού αλγορίθμου Sieve of Eratosthenes είναι O(n*log(log(n))). Η συλλογιστική πίσω από αυτήν την πολυπλοκότητα συζητείται παρακάτω.

Για έναν δεδομένο αριθμό n, ο χρόνος που απαιτείται για να επισημανθεί ένας σύνθετος αριθμός (δηλαδή, ένας μη πρώτος αριθμός) είναι σταθερός. Έτσι, ο αριθμός των φορών που εκτελείται ο βρόχος είναι ίσος με:

n/2 + n/3 + n/5 + n/7 + ……∞

= n * (1/2 + 1/3 + 1/5 + 1/7 +…….∞)

Η αρμονική πρόοδος του αθροίσματος των πρώτων αριθμών μπορεί να συναχθεί ως log(log(n)):

(1/2 + 1/3 + 1/5 + 1/7 +…….∞) = log(log(n))

Έτσι, η χρονική πολυπλοκότητα θα είναι:

T(n) = n * (1/2 + 1/3 + 1/5 + 1/7 + ……∞)

= n * log(log(n))

Έτσι, η χρονική πολυπλοκότητα είναι O(n * log(log(n))).

Στη συνέχεια, θα μάθετε για Το Τρίγωνο του Πασκάλ.

Συχνές Ερωτήσεις