Problema
La congettura di Goldbach afferma che ogni numero pari maggiore di 2 è la somma di due numeri primi. Non è mai stata dimostrata, ma è stata verificata ben oltre i numeri di questo esercizio. Spesso i modi possibili sono più di uno: 28 = 5 + 23 = 11 + 17. Trova quello in cui il primo più piccolo è il minore possibile.
Implementa goldbach_partition(n).
Provare p = 2, 3, 5, ... e controllare se n − p è primo porta subito alla risposta, perché un p piccolo funziona quasi sempre. Per verificare se un numero fino a 10^9 è primo con il metodo delle divisioni successive bastano i divisori fino a circa 31 623.
Input
n: un numero pari maggiore di 2.
Output
Restituisci [p, q], dove p e q sono primi, p + q = n, p ≤ q e p è il primo più piccolo per cui questo funziona.
Vincoli
4 ≤ n ≤ 10^9, n è pari
Esempi
Input:
n = 28
Output atteso:
expected = [5, 23]
Input:
long long n = 28;
Output atteso:
std::vector<long long> expected = {5, 23};
Input:
long n = 28;
Output atteso:
long[] expected = new long[] {5, 23};
Spiegazione
28 − 2 = 26 e 28 − 3 = 25 non sono primi, mentre 28 − 5 = 23 lo è, quindi la risposta è [5, 23].
Input:
n = 4
Output atteso:
expected = [2, 2]
Input:
long long n = 4;
Output atteso:
std::vector<long long> expected = {2, 2};
Input:
long n = 4;
Output atteso:
long[] expected = new long[] {2, 2};
Spiegazione
L'unica possibilità è 2 + 2, quindi la risposta è [2, 2].
Come affrontarlo
Prova prima da solo, poi apri un suggerimento alla volta.
Suggerimento 1
Prova p = 2, 3, 4, ... e fermati al primo p per cui sia p sia n − p sono primi.
Suggerimento 2
Un test di primalità deve provare i divisori solo fino alla radice quadrata.
Suggerimento 3
Dato che ti fermi al p più piccolo, la condizione p ≤ n − p è soddisfatta automaticamente.
Complessità attesa
tempo O(k √n), dove k è il numero di candidati provati, spazio aggiuntivo O(1)
Riferimenti
Questa sfida è adattata per CodeUtility. Segui la traccia e i vincoli sopra.