Problema
Algumas expressões quadráticas são boas em gerar primos. n² + n + 41 dá primos para n de 0 a 39. Para inteiros a e b com |a| ≤ limit e |b| ≤ limit, conte quantos valores consecutivos n = 0, 1, 2, ... tornam n² + an + b primo, parando no primeiro valor que não for primo. Encontre o par com a maior sequência.
Implemente quadratic_primes(limit).
Entrada
limit: o limite para os valores absolutos de a e b.
Saída
Retorne [a, b, run], em que run é a quantidade de primos na maior sequência. Em caso de empate, escolha o menor a e, depois, o menor b. Números menores que 2 não são primos, então um par cujo valor em n = 0 não é primo tem sequência 0.
Restrições
0 ≤ limit ≤ 300
Exemplos
Entrada:
limit = 3
Saída esperada:
expected = [-2, 3, 3]
Entrada:
long long limit = 3;
Saída esperada:
std::vector<long long> expected = {-2, 3, 3};
Entrada:
long limit = 3;
Saída esperada:
long[] expected = new long[] {-2, 3, 3};
Explicação
Com a = −2 e b = 3, os valores para n = 0, 1, 2, 3 são 3, 2, 3, 6: três primos. Nenhum par faz melhor e nenhum a menor empata, então a resposta é [-2, 3, 3].
Entrada:
limit = 1
Saída esperada:
expected = [-1, -1, 0]
Entrada:
long long limit = 1;
Saída esperada:
std::vector<long long> expected = {-1, -1, 0};
Entrada:
long limit = 1;
Saída esperada:
long[] expected = new long[] {-1, -1, 0};
Explicação
b é −1, 0 ou 1 e nenhum deles é primo, então toda sequência é 0 e o menor par vence: [-1, -1, 0].
Como abordar
Tente sozinho primeiro e depois abra uma dica de cada vez.
Dica 1
Em n = 0 o valor é b, então b precisa ser primo para haver qualquer sequência.
Dica 2
Aumente n até o valor não ser primo; valores negativos e menores que 2 encerram a sequência.
Dica 3
Percorra a e b em ordem crescente e só troque o melhor par quando a sequência for estritamente maior.
Complexidade esperada
tempo O(limit² × run × √V), espaço extra O(1)
Referências
Este desafio foi adaptado para o CodeUtility. Siga o enunciado e as restrições acima.