Todos los desafíos
Intermedio 0 resueltos 0% de aceptación

Primos cuadráticos

Encuentra la expresión cuadrática n² + an + b que da la racha más larga de primos a partir de n = 0.

Lo que aprenderás

  • Comprobar la primalidad por división por tentativa
  • Explorar un espacio de dos parámetros
  • Aplicar reglas de desempate

Problema

Ver original (inglés)

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

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

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

Clasificación

Clasificación completa

La mejor solución aprobada de cada programador. Las más rápidas, ligeras y mejor valoradas van primero.

Aún no hay soluciones aprobadas. Resuélvelo y quédate el primer puesto.

Aprende de otros

Soluciones de la comunidad

Aún no hay soluciones publicadas. Resuelve este reto para compartir la primera.