Todos os desafios
Médio 0 resolvidos 0% de aceitação

Primos quadráticos

Encontre a expressão quadrática n² + an + b que gera a maior sequência de primos a partir de n = 0.

O que você vai aprender

  • Testar a primalidade por divisão por tentativa
  • Explorar um espaço de dois parâmetros
  • Aplicar regras de desempate

Problema

Ver original (inglês)

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

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

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

A melhor solução aprovada de cada programador. As mais rápidas, leves e mais bem avaliadas ficam no topo.

Ainda não há soluções aprovadas. Resolva e fique com o primeiro lugar.

Aprenda com outros

Soluções da comunidade

Ainda não há soluções publicadas. Resolva este desafio para compartilhar a primeira.