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: *****  / 19
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ć
photo
0 # marcin7777777 2020-01-28 12:05
Pewnie znalazłeś już odpowiedź, ale i tak odpiszę:-). Najprawdopodobn iej korzystasz z pythona 3.x. Zamień po prostu raw_input na samo input, ponadto po print wpisz zmieną w nawiasach okrągłych. Pzdr
Odpowiedz | Odpowiedz z cytatem | Cytować
photo
0 # Nowy 2019-11-13 22:17
Może i nie długo piszę w pythonie, ale już spotkałem się z wyzwaniem napisania programu wyszukującego liczby pierwsze. Praca na listach z liczbami jest bardzo wygodna, i jeszcze jak są z odstępami co 1, to już wogóle. Ale problem się pojawia gdy chcemy nasz program przetestować w boju, i zamiast normalnych 100 lub 1000 wpiszemy milion, albo 10 milionów. Dlatego operacja na liście, która jest opisana zero jedynkowo albo True False ogranicza bardzo potrzebną ilość operacji, bo pamiętajmy że wszystkie operacje są dokonywane biarnie, a 6 cyfrowa, niby nie długa liczba zajmuje pare bajtów, a to tylko jedna liczba na milion. Jeżeli poszłoby się klasycznym sitem Eratostenesa, czyli znalezienie liczby pierwszej i wykreślanie jej wielokortności (no po prostu z 1 robienie 0 odpowiadającym im liczbom, więc cała magia potem w odczycie tej listy tak, żeby wyszedł dobry wynik). Dodając jeszcze że zaczynamy wykreślaś od kwadratu liczby, a w sumie to nie potrzebujemy wcale parzystych-lista krótsza x2
Odpowiedz | Odpowiedz z cytatem | Cytować
Dodaj komentarz