Corso Online per Potenziare le Competenze Digitali
La congettura di Goldbach afferma che: ogni numero pari (maggiore di 2) è ottenibile come somma di due numeri primi.
Per esempio, 16 è la somma di 11 e 5, mentre 20 è la somma di 17 e 3.
Il vostro compito è quello di scrivere un programma che, letto un numero pari, stampi due numeri primi la cui somma corrisponda al numero letto.
Esempi di input/output
+-----------+-------------+
| input.txt | output.txt |
+----+-----------+-------------+
| 1° | 16 | 3 13 (5 11) |
+----+-----------+-------------+
| 2° | 20 | 3 17 (7 13) |
+----+-----------+-------------+
Funzione primo():
- se esiste y in [2, x-1] che divide x allora x non è primo
- se non esiste y … allora x è primo
Main:
- la prima coppia è (2, n-2)
- il ciclo while scorre tutte le coppie (n1, n2) con n1+n2=n e n1 <= n2
- se n1 è primo e n2 è primo allora stampa la coppia
def primo(x):
for y in range(2,x):
if(x%y == 0):
return False
return True
n = 20 # pari e maggiore di 2
n1 = 2
n2 = n-2
while(n1 <= n2):
if(primo(n1) and primo(n2)):
print(n1, n2)
n1+=1
n2-=1
Risultato
3 17
7 13
Il ciclo while si interrompe, con break, quando viene individuata la prima coppia di numeri primi
...
while(n1 <= n2):
if(primo(n1) and primo(n2)):
print(n1, n2)
break
n1+=1
n2-=1
La struttura del ciclo while può essere semplificata?
...
while(n1 <= n2) and (not primo(n1)) or (not primo(n2)):
n1+=1
n2-=1
if(n1 <= n2):
print(n1,n2)
Se la congettura è vera…
...
while(not primo(n1)) or (not primo(n2)):
n1+=1
n2-=1
print(n1, n2)
Si può rendere ancora più veloce?
- Dopo aver controllato il 2, scorrere solo i numeri dispari
- Crivello di Eratostene
- …
- L’argomento è tra i più studiati della matematica!