Problème
Certains trinômes du second degré produisent beaucoup de nombres premiers. n² + n + 41 donne des nombres premiers pour n allant de 0 à 39. Pour des entiers a et b avec |a| ≤ limit et |b| ≤ limit, comptez combien de valeurs consécutives n = 0, 1, 2, ... rendent n² + an + b premier, en vous arrêtant à la première valeur qui ne l'est pas. Trouvez le couple qui donne la plus longue série.
Implémentez quadratic_primes(limit).
Entrée
limit : la borne sur les valeurs absolues de a et b.
Sortie
Renvoyez [a, b, run], où run est le nombre de nombres premiers de la plus longue série. En cas d'égalité, prenez le plus petit a, puis le plus petit b. Les nombres inférieurs à 2 ne sont pas premiers, donc un couple dont la valeur en n = 0 n'est pas première a une série de longueur 0.
Contraintes
0 ≤ limit ≤ 300
Exemples
Entrée :
limit = 3
Sortie attendue :
expected = [-2, 3, 3]
Entrée :
long long limit = 3;
Sortie attendue :
std::vector<long long> expected = {-2, 3, 3};
Entrée :
long limit = 3;
Sortie attendue :
long[] expected = new long[] {-2, 3, 3};
Explication
Avec a = −2 et b = 3, les valeurs pour n = 0, 1, 2, 3 sont 3, 2, 3, 6 : trois nombres premiers. Aucun couple ne fait mieux et aucun a plus petit ne fait aussi bien, donc la réponse est [-2, 3, 3].
Entrée :
limit = 1
Sortie attendue :
expected = [-1, -1, 0]
Entrée :
long long limit = 1;
Sortie attendue :
std::vector<long long> expected = {-1, -1, 0};
Entrée :
long limit = 1;
Sortie attendue :
long[] expected = new long[] {-1, -1, 0};
Explication
b vaut −1, 0 ou 1, et aucune de ces valeurs n'est première : toutes les séries ont une longueur 0 et c'est le plus petit couple qui l'emporte, [-1, -1, 0].
Comment l'aborder
Essayez d'abord seul, puis ouvrez les indices un par un.
Indice 1
En n = 0, la valeur est b, donc b doit être premier pour qu'il y ait une série.
Indice 2
Augmentez n jusqu'à ce que la valeur ne soit plus première ; les valeurs négatives et celles inférieures à 2 mettent fin à la série.
Indice 3
Parcourez a et b dans l'ordre croissant et ne remplacez le meilleur couple que pour une série strictement plus longue.
Complexité attendue
temps O(limit² × run × √V), espace supplémentaire O(1)
Références
Ce défi a été adapté pour CodeUtility. Suivez l'énoncé et les contraintes ci-dessus.