Αλγόριθμος Κοσκινού Ερατοσθένη: Python, C++ Παράδειγμα

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

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

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

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

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

Ας πάρουμε το εύρος των αριθμών από το 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.

Ψευδοκώδικας

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++ Παράδειγμα κώδικα

#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 Παράδειγμα προγράμματος

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)

Παραγωγή:

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

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

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

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

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

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

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

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

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

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

Η χρονική πολυπλοκότητα ενός αλγορίθμου κανονικού κόσκινου ερατοσθένη είναι 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)))

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

Περίληψη

Το κόσκινο του Ερατοσθένη φιλτράρει τους πρώτους αριθμούς σε ένα δεδομένο ανώτερο όριο.
Το φιλτράρισμα ενός πρώτου αριθμού ξεκινά από τον μικρότερο πρώτο αριθμό, "2". Αυτό γίνεται επαναληπτικά.
Η επανάληψη γίνεται μέχρι την τετραγωνική ρίζα του n, όπου n είναι το δεδομένο εύρος αριθμών.
Μετά από αυτές τις επαναλήψεις, οι αριθμοί που απομένουν είναι οι πρώτοι αριθμοί.