Sto cercando l'algormitmo che, dato di input un numero, restituisca True se è primo e False se non lo è.
Ci sono riuscito, ma senza applicare la funzione ricorsiva:
CODICE
def VerificaPrimi(x):
c=True
i=2
while i<=(x-1)/2 and c==True:
if x%i!=0:
i=i+1
else:
c=False
if c==False:
return False
else:
return True
x=int(raw_input())
print VerificaPrimi(x)
Solo che questo non mi soddisfa perchè fa dei calcoli inutili... ammettendo che si inserisca il numero 23, prova a dividerlo per 2, poi per 3, e fin qui è corretto, poi per 4, e qui non va bene perchè se non è divisibile per due non lo è nemmeno per 4, ed è un calcolo risparmiabile, poi lo divide per 5 e va bene, poi per 6, ed è un altro calcolo inutile perchè se non è divisibile ne per 2 ne per 3 non lo è nemmeno per 6.
Quindi ho pensato che ha senso provare a dividere il numero inserito soltanto per i numeri primi inferiori alla sua metà che lo precedono, in questo modo il numero di calcoli che python deve effettuare diminuisce enormemente, soprattutto in caso di un valore di input molto elevato.
E quindi ho fatto questo:
CODICE
def VerificaPrimi(x):
c=True
i=2
while i<=x/2 and c==True:
if VerificaPrimi(i)==True:
if x%i!=0:
i=i+1
else:
c=False
if c==False:
return False
else:
return True
i=i+1
x=int(raw_input())
print VerificaPrimi(x)
Inizialmente sembra funzionare, ma stranamente da un certo valore in poi (mi pare il 17) mi pare che restituisca soltanto False per i numeri pari immessi, mentre per tutti i dispari (primi o no) non restituisce nulla, e non capisco perchè : \
Igitur te voco, Wet Water, ut ducas me recto iteris.
.