Πηγές:
http://users.sch.gr/geoman22/mathP/Eratosthenis.htm
https://el.wikipedia.org/wiki/Κόσκινο_του_Ερατοσθένη
Επίσης σε Linux based διανομές μπορείτε να κάνετε έπαλήθευση και με το command line tools ‘primes’ που θα βρείτε στο πακέτο bsdgames.
# -*- coding: utf-8 -*- N = input("Δώσε N:") # χρειαζόμαστε μια λίστα που να γεμίσει με ακεραίους από 1 εως Ν lista = range(0,N+1) print lista # πρέπει να βρίσκουμε τα πολλαπλάσια ενός αριθμού και να τα αφαιρούμε # από τη λίστα. Ίσως μπορούμε να κερδίσουμε χρόνο αν # υπάρχει αντιστοιχία θέσεων στη λίστα με την τιμή. Δηλαδή ο αριθμός # 5 είναι στην 5η θέση. p = lista[2] # ο εξεταζόμενος αριθμός i = 1 # μετρητής για τον υπολογισμό των πολλαπλάσιων k = 0 # pollaplasia ypopsifioy protoy p j = 3 # πόσα περάσματα πρέπει να κάνουμε; synexizoyme oso p^2 einan < N while p*p < N : # όσο ισχύει αυτή η συνθήκη βρισκουμε τα πολλαπλασια του p kai τα αφαιρουμε από το την λίστα i = 2 k = 0 while i <= N and k <= N: # διατρεχουμε τη λιστα και αφαιρουμε τα πολλαπλασια του p k = i*p # η αρχική τιμή του i πρέπει να είναι 2 # print k if k <= N: lista[k] = 0 i = i + 1 print "μετά τη διαγραφή των πολλαπλάσιων του ",p , " ή λίστα είναι", lista # euresi toy epomenoy ypopsifiou protoy p foundnextp = False j = p while foundnextp == False : if lista[j+1] != 0: p = j + 1 foundnextp = True else: j = j + 1 print "*************************************" print "Οι πρώτοι μικρότεροι του : ",N print lista for i in range(0,N+1): if lista[i] != 0: print lista[i]
Ετικέτες:github, Python, μαθηματικά