Problema
Algunas expresiones cuadráticas generan primos con facilidad: n² + n + 41 da primos para n = 0 a 39. Para enteros a y b con |a| ≤ limit y |b| ≤ limit, cuenta cuántos valores consecutivos n = 0, 1, 2, ... hacen que n² + an + b sea primo, deteniéndote en el primer valor que no lo sea. Encuentra el par con la racha más larga.
Implementa quadratic_primes(limit).
Entrada
limit: la cota de los valores absolutos de a y b.
Salida
Devuelve [a, b, run], donde run es la cantidad de primos de la racha más larga. Si varios pares empatan, elige el menor a y, después, el menor b. Los números menores que 2 no son primos, así que un par cuyo valor en n = 0 no es primo tiene una racha de 0.
Restricciones
0 ≤ limit ≤ 300
Ejemplos
Entrada:
limit = 3
Salida esperada:
expected = [-2, 3, 3]
Entrada:
long long limit = 3;
Salida esperada:
std::vector<long long> expected = {-2, 3, 3};
Entrada:
long limit = 3;
Salida esperada:
long[] expected = new long[] {-2, 3, 3};
Explicación
Con a = −2 y b = 3, los valores para n = 0, 1, 2, 3 son 3, 2, 3, 6: tres primos. Ningún par lo supera ni empata con un a menor, así que la respuesta es [-2, 3, 3].
Entrada:
limit = 1
Salida esperada:
expected = [-1, -1, 0]
Entrada:
long long limit = 1;
Salida esperada:
std::vector<long long> expected = {-1, -1, 0};
Entrada:
long limit = 1;
Salida esperada:
long[] expected = new long[] {-1, -1, 0};
Explicación
b solo puede ser −1, 0 o 1 y ninguno es primo, así que todas las rachas son 0 y gana el par más pequeño: [-1, -1, 0].
Cómo abordarlo
Inténtalo primero por tu cuenta y luego abre las pistas una a una.
Pista 1
En n = 0 el valor es b, así que b tiene que ser primo para que haya alguna racha.
Pista 2
Aumenta n hasta que el valor no sea primo; los valores negativos y los menores que 2 terminan la racha.
Pista 3
Recorre a y b en orden creciente y cambia el mejor solo cuando la racha sea estrictamente más larga.
Complejidad esperada
tiempo O(limit² × run × √V), espacio extra O(1)
Referencias
Este reto está adaptado para CodeUtility. Sigue el enunciado y las restricciones indicadas arriba.