Tous les défis
Moyen 0 résolus 0 % de réussite

Trinômes générateurs de nombres premiers

Trouver le trinôme n² + an + b qui donne la plus longue suite de nombres premiers à partir de n = 0.

Ce que vous allez apprendre

  • Tester la primalité par divisions successives
  • Explorer un espace à deux paramètres
  • Appliquer des règles de départage

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

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

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

La meilleure solution validée de chaque codeur. Les plus rapides, les plus légères et les mieux notées passent devant.

Aucune solution validée pour l'instant. Résolvez-le et prenez la première place.

Apprenez des autres

Solutions de la communauté

Aucune solution publiée pour l'instant. Résolvez ce défi pour partager la première.