algorytm.org

Implementacja w Python

Baza Wiedzy
wersja offline serwisu przeznaczona na urządzenia z systemem Android
Darowizny
darowiznaWspomóż rozwój serwisu
Nagłówki RSS
Artykuły
Implementacje
Komentarze
Forum
Bookmarki






Sonda
Implementacji w jakim języku programowania poszukujesz?

Sito Eratostenesa - Implementacja w Python
Ocena użytkownikóww: *****  / 12
SłabyŚwietny
Nadesłany przez Kamil Socha, 26 listopada 2012 22:14
Kod przedstawiony poniżej przedstawia główną część rozwiązania problemu.
Pobierz pełne rozwiązanie.

sito_eratostenesa.py:
#Sito Eratostenesa - poszukiwanie liczb pierwszych
#www.algorytm.org

from math import sqrt

#tworzy tablice z wartosciami od "od" (wlacznie) do "do" (wlacznie)
def od_do(od, do):
    zw=[]
    while od!=do+1:
        zw.append(od)
        od+=1
    return zw

#sito Eratostenesa dla liczb od 1 do "do"
def sito(do):
    sq = int(sqrt(do)) #gorny zakres dzialania algorytmu
    obecnie=1          #wartosc poczatkowa 
    tab=od_do(1, do)   #utworz tablice z wartosciami od 1 do "do"
    while True:
        if obecnie>sq: #warunek zakonczenia dzialania algorytmu
            return tab

        for i in tab:  #dla wszystkich liczb w tablicy
            #usun element jezeli jest podzielny przez obecna liczbe
            if (not(i%obecnie) and not(obecnie==i)) and obecnie!=1: 
                tab.remove(i)

        i = tab.index(obecnie)+1
        obecnie = tab[i]
        
#pobierz od uzytkownika gorny zakres dzialania algorytmu i wypisz wyniki
n = int(raw_input("Podaj gorny zakres dzialania sita: "))
pierwsze = sito(n)
for pierwsza in pierwsze:
        print pierwsza
Komentarze
photo
0 # Wojtek87 2018-02-22 14:15
A jak zmodyfikować aby można uzyskać odpowiedź nie od 0 lecz od danej(podanej) liczby ?
Odpowiedz | Odpowiedz z cytatem | Cytować
photo
0 # Jarecki RZ 2018-09-27 10:15
Korzystając z założenia że liczba pierwsza (dla liczb większych od 10) zawsze kończy się 1,3,7,9 można zopytmalizować powyższy algorytm i tablicę od_do wypełniać tylko takimi które tak się kończą

def od_do(od, do): # optimalized
zw=[]
while od!=do+1:
if od > 10:
if str(od)[-1:] in ['1','3','7','9']:
zw.append(od)
else:
zw.append(od)
od+=1
return zw

Dla n = 100000 liczby pierwsze zostaną obliczone w około 5s natomiast bez optymalizacji w około 28s
Odpowiedz | Odpowiedz z cytatem | Cytować
photo
0 # Nie działa 2019-02-24 18:30
Nie działa, n = int(raw_input("Podaj gorny zakres dzialania sita: "))
NameError: name 'raw_input' is not defined
Odpowiedz | Odpowiedz z cytatem | Cytować
Dodaj komentarz