Πηγές:

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

Ετικέτες:github, Python, μαθηματικά