Problema
Alcuni polinomi di secondo grado sono bravi a generare numeri primi: n² + n + 41 dà primi per n da 0 a 39. Per interi a e b con |a| ≤ limit e |b| ≤ limit, conta quanti valori consecutivi n = 0, 1, 2, ... rendono primo n² + an + b, fermandoti al primo valore che non è primo. Trova la coppia con la sequenza più lunga.
Implementa quadratic_primes(limit).
Input
limit: il limite per i valori assoluti di a e b.
Output
Restituisci [a, b, run], dove run è il numero di primi nella sequenza più lunga. In caso di parità, scegli la a più piccola e poi la b più piccola. I numeri minori di 2 non sono primi, quindi una coppia il cui valore per n = 0 non è primo ha una sequenza di lunghezza 0.
Vincoli
0 ≤ limit ≤ 300
Esempi
Input:
limit = 3
Output atteso:
expected = [-2, 3, 3]
Input:
long long limit = 3;
Output atteso:
std::vector<long long> expected = {-2, 3, 3};
Input:
long limit = 3;
Output atteso:
long[] expected = new long[] {-2, 3, 3};
Spiegazione
Con a = −2 e b = 3 i valori per n = 0, 1, 2, 3 sono 3, 2, 3, 6: tre primi. Nessuna coppia fa meglio e nessuna a più piccola pareggia, quindi la risposta è [-2, 3, 3].
Input:
limit = 1
Output atteso:
expected = [-1, -1, 0]
Input:
long long limit = 1;
Output atteso:
std::vector<long long> expected = {-1, -1, 0};
Input:
long limit = 1;
Output atteso:
long[] expected = new long[] {-1, -1, 0};
Spiegazione
b vale −1, 0 o 1 e nessuno di questi è primo, quindi ogni sequenza ha lunghezza 0 e vince la coppia più piccola: [-1, -1, 0].
Come affrontarlo
Prova prima da solo, poi apri un suggerimento alla volta.
Suggerimento 1
Per n = 0 il valore è b, quindi b deve essere primo perché ci sia una sequenza.
Suggerimento 2
Fai crescere n finché il valore non è più primo; i valori negativi e quelli minori di 2 chiudono la sequenza.
Suggerimento 3
Scorri a e b in ordine crescente e sostituisci la migliore solo con una sequenza strettamente più lunga.
Complessità attesa
tempo O(limit² × run × √V), spazio aggiuntivo O(1)
Riferimenti
Questa sfida è adattata per CodeUtility. Segui la traccia e i vincoli sopra.