Tutte le sfide
Media 0 risolte 0% di accettazione

Congettura di Goldbach

Scrivi un numero pari come somma di due primi, scegliendo il primo addendo più piccolo possibile.

Cosa imparerai

  • Scrivere un test di primalità per divisioni successive che si ferma a √n
  • Provare i candidati in ordine crescente e fermarsi al primo che funziona
  • Restituire una coppia nell'ordine richiesto

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

Esempio 1
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].

Esempio 2
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.

La migliore soluzione superata di ogni programmatore. Le più veloci, leggere e meglio valutate stanno in alto.

Ancora nessuna soluzione superata. Risolvila e prendi il primo posto.

Impara dagli altri

Soluzioni della community

Nessuna soluzione pubblicata. Risolvi questa sfida per condividere la prima.