Crivello di Eratostene PY

di
f123c
il
6 risposte
F
f123c
Pochi posts
Iscritto da
lug, 2022
Messaggi:
2

Crivello di Eratostene PY

Ciao a tutti,
sto imparando da poco ad usare python,
ho controllato e mi sembra di non aver discussioni su questo argomento in questa categoria,
detto ciò stavo scrivendo questo esercizio che però funziona parzialmente,
def Eratostene(n):
    setaccio = list(range(2, n+1))
    n_primi = []
    for s in setaccio:
        p = setaccio.pop(0)
        n_primi.append(p)
        for s in setaccio:
            if s%p == 0: setaccio.remove(s)
        if setaccio == []: break
    return n_primi
>>> Eratostene(30)
< [2, 3, 5, 7, 11] >

riuscite a darmi una mano a capire dove sbaglio?
Grazie
FC

6 Risposte

  • S
    Soldino
    Pochi posts
    Iscritto da
    lug, 2022
    Messaggi:
    13

    Re: Crivello di Eratostene PY

    Ciao.
    Ho l'impressione che ci sia una qualche interferenza tra i due cicli for.
    Io ho preferito ristrutturare la funzione in questo modo.
    Come puoi vedere, adesso c'è un solo ciclo for che rimuove anche il primo valore della lista senza ricorrere al .pop del setaccio.
    Fai sapere.
    
def Eratostene(n):
    setaccio = list(range(2, n+1))
    n_primi = []
    while setaccio != []:
        p = setaccio[0]
        n_primi.append(p)
        for s in setaccio:
            if s%p == 0: setaccio.remove(s)
    return n_primi
  • Andrea Quaglia
    Andrea Quaglia
    Molto attivo
    Iscritto da
    giu, 2017
    Messaggi:
    614

    Re: Crivello di Eratostene PY

    Secondo me l'implementazione del crivello non è corretta. L'algoritmo prevede che dopo aver trovato un numero primo, dalla lista si eliminino tutti i multipli di quel numero primo, poi si passi all'elemento successivo, che sarà un numero primo, e si eliminano tutti gli elementi multipli, e così via sino a terminare la lista. Alla fine la lista sarà composta solo da numeri primi.
    Quindi ho fatto la seguente implementazione:
    def Eratostene(n):
    setaccio = list(range(2, n+1))
    i = 0
    while i < len(setaccio):
        for s in setaccio:
            if s % setaccio[i] == 0 and s != setaccio[i]:
                # non è primo, elimino
                setaccio.remove(s)
        i += 1

    return setaccio
    Non è bello né efficiente (il 'for s in setaccio' ripassa la lista dall'inizio ogni volta, e non è necessario).
    Questa versione è più efficiente (anche se c'è poco Python e molto C):
    def Eratostene(n):
    setaccio = list(range(2, n+1))
    i = 0
    j = 1
    while i < len(setaccio):
        while j < len(setaccio):
            if setaccio[j] % setaccio[i] == 0:
                # non è primo, elimino
                setaccio.remove(setaccio[j])
            else:
                j += 1
        i += 1
        j = i + 1

    return setaccio
  • M
    migliorabile
    Super Famoso
    Iscritto da
    apr, 2013
    Messaggi:
    6020

    Re: Crivello di Eratostene PY

    La ""rimozione fisica"" non sarebbe neccessaria (in linguaggi come Java questo genererebbe non pochi inconvenienti ).
    Si puo' anche solo ""marcare"" il numero come ""non primo"", ad esempio rimpiazzandolo con 1.

    In origine, l'algoritmo consisteva priprio nel MARCARE i NON PRIMI.

    https://it.wikipedia.org/wiki/Crivello_di_Eratosten
  • S
    Soldino
    Pochi posts
    Iscritto da
    lug, 2022
    Messaggi:
    13

    Re: Crivello di Eratostene PY

    In realtà, il ciclo for non mi pare poco efficiente poiché esamina una lista dinamica alla quale vengono rimossi, di volta in volta, gli elementi primi, poi trasferiti in una seconda lista che rappresenta il risultato finale.
    Nei cicli che di volta in volta si avvicendano, quindi, non c'è ridondanza nell'esame degli elementi della lista.
    Facendo un esempio, al primo passaggio la lista potrebbe essere [2,3,4,5,6,7,8,9,10]. Gli elementi da esaminare sono nove e, alla fine del ciclo, la lista diventa [3,5,7,9].
    Al passaggio successivo la lista è cambiata e si riparte con un nuovo ciclo che avviene sugli esatti elementi da analizzare. Non mi sembra che ci sia alcuna ridondanza nell'analisi dei dati.
    Nemmeno dal punto di vista dell'occupazione di memoria mi sembra che ci sia particolare inefficienza, dal momento che in un dato istante le due liste complessivamente contengono un numero sempre minore di dati.
    Mi sembra, così, che la soluzione ideata da f123c, al netto degli errori di implementazione, non sia affatto male.
    L'unico appunto, ma più formale che sostanziale, che forse si potrebbe muovere è nell'impiego di due liste anziché di una soltanto.
    In ciò, tuttavia, non mi pare ci sia nulla di inefficiente e, anzi, mi sembra si possa riferire ad uno stile personale di approccio alla problematica.
  • F
    f123c
    Pochi posts
    Iscritto da
    lug, 2022
    Messaggi:
    2

    Re: Crivello di Eratostene PY

    Ciao e grazie a tutti per le risposte e i consigli, mi avete dato degli spunti interessanti da cui ripartire. La prossima volta spero di potervi aiutare io, ma se ne riparlerà tra un po' di tempo suppongo
  • C
    claugoit
    Pochi posts
    Iscritto da
    giu, 2021
    Messaggi:
    24

    Re: Crivello di Eratostene PY

    Se ti interessa questo codice, molto semplice, applica il Crivello su un range di 500 milioni partendo da una qualsiasi cifra pari
    che in questo caso è "nbb=105000000000 ".
    Lo scopo del programma è individuare tutti i numeri primi che si trovano dentro questo range e cioè da (nbb a nbb+500000000)
    e memorizzarli dentro un file (ava=1) che si incrementa a seconda di quanti cicli vuoi far fare al programma (while ava<=1:)
    Per ogni ciclo ci vogliono circa 10 minuti, naturalmente questo dipende anche dal tipo di computer che usi e dalla grandezza del numero di partenza, e puoi partire da un qualsiasi numero pari senza dover sempre partire da 1.
    Tieni presente che i numeri primi da analizzare su un range di 500.000.000 sono comunque meno della metà se tolti i numeri pari e i numeri che finiscono con 5.

    Nap=? è il numero da cui vuoi cominciare a memorizzare i file con i numeri primi
    Se ad esempio nap=15 e (while ava<=10), i file che memorizzerà il programma partiranno da 15 fino a 25, questo per permetterti di memorizzare file di numeri primi interrompendo e riprendendo il programma a tuoi piacimento
    
#Crivello
from datetime import datetime
import math
now = datetime.now().time()
print("ora inizio =", now)
#***************************
nbb=105000000000
ava=1
nap=1
matrice=[]
limite=500000000
print('riempimento matrice')
for i in range(limite):
    matrice.append(0)
while ava<=1:
    nb=nbb
    print('---------------->',nb)
    nb=nb//30*30
    limite=limite//30*30
    np=2
    npp=3
    cont=1 
    limite2=nb+limite
    print('prima parte')
    while cont>0:
        if np%2==0:
            n=npp*np+1
        else:
            n=npp*np+2

        t1=nb//n
        if (t1-1)%3==0:
            molt=(t1-1)//3
        if (t1-2)%3==0:
            molt=(t1-2)//3
        if (t1-3)%3==0:
            molt=(t1-3)//3

        if n*n>limite2:
            break

        cont2=1
        molt3=3
        while cont2>0:
            if molt%2==0:
                a=molt3*molt+1
            else:
                a=molt3*molt+2
            if n*a>limite2:
                break
            if a>n and n*a%5!=0 and n*a>nb:
                matrice[n*a-nb]=n*a-nb
#              print(n,"x",a,"=",n*a,'----->',n*a-nb)
            molt=molt+1
        
        np=np+1
#-------------------------------------------
    print('parte finale')
    scrivi=open(str(nap)+'.txt','w')
    dividi=0
    qt=0
    for i in range(limite):
        if matrice[i]==0 and i%2!=0 and i%5!=0:
            if (i+nb)%3!=0:
                #print(i+nb)
                scrivi.write(str(i+nb)+' ')
                dividi=dividi+1
                qt=qt+1
            if dividi==28:
                scrivi.write('\n')
                dividi=0
        matrice[i]=0    

    scrivi.close()    
    print('-------------------------')
    print('numeri primi ',qt)
    print('-------------------------')
    now = datetime.now().time()
    print("ora fine =", now)
    limite=500000000
    nbb=nbb+limite
    ava=ava+1
    nap=nap+1
Devi accedere o registrarti per scrivere nel forum
6 risposte