Tutte le sfide
Media 0 risolte 0% di accettazione

Primi quadratici

Trova il polinomio n² + an + b che genera la sequenza di primi più lunga a partire da n = 0.

Cosa imparerai

  • Verificare la primalità con le divisioni successive
  • Esplorare uno spazio a due parametri
  • Applicare le regole di spareggio

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

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

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

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.