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

Nombres premiers jumeaux

Listez tous les couples de nombres premiers jumeaux (p, p + 2) jusqu'à une limite.

Ce que vous allez apprendre

  • Marquer les nombres premiers jusqu'à une limite avec un crible
  • Repérer les nombres premiers espacés de deux
  • Gérer les limites trop petites pour contenir un couple

Problème

Des nombres premiers jumeaux sont deux nombres premiers dont la différence vaut 2, comme 11 et 13 ou 17 et 19. Trouvez tous les couples de ce type dont le plus grand nombre ne dépasse pas limit.

Implémentez twin_primes(limit).

Pour les grandes limites, trouvez tous les nombres premiers d'un coup avec un crible au lieu de tester chaque nombre séparément.

Entrée

limit : la plus grande valeur autorisée pour le plus grand nombre premier d'un couple.

Sortie

Renvoyez une liste de couples [p, p + 2] où les deux nombres sont premiers et p + 2 ≤ limit, triés par p croissant. S'il n'y en a aucun, renvoyez une liste vide.

Contraintes

0 ≤ limit ≤ 10^6

Exemples

Exemple 1
Entrée :
limit = 20

Sortie attendue :
expected = [
    [3, 5],
    [5, 7],
    [11, 13],
    [17, 19]
]
Entrée :
long long limit = 20;

Sortie attendue :
std::vector<std::vector<long long>> expected = {
    {3, 5},
    {5, 7},
    {11, 13},
    {17, 19}
};
Entrée :
long limit = 20;

Sortie attendue :
long[][] expected = new long[][] {
    new long[] {3, 5},
    new long[] {5, 7},
    new long[] {11, 13},
    new long[] {17, 19}
};

Explication

Les nombres premiers jusqu'à 20 sont 2, 3, 5, 7, 11, 13, 17, 19, et ceux qui sont espacés de 2 donnent [[3, 5], [5, 7], [11, 13], [17, 19]].

Exemple 2
Entrée :
limit = 6

Sortie attendue :
expected = [
    [3, 5]
]
Entrée :
long long limit = 6;

Sortie attendue :
std::vector<std::vector<long long>> expected = {
    {3, 5}
};
Entrée :
long limit = 6;

Sortie attendue :
long[][] expected = new long[][] {
    new long[] {3, 5}
};

Explication

3 et 5 sont premiers et 5 ≤ 6, mais 7 dépasse la limite, donc seulement [[3, 5]].

Comment l'aborder

Essayez d'abord seul, puis ouvrez les indices un par un.

Indice 1

Un crible trouve tous les nombres premiers jusqu'à 10^6 bien plus vite que de tester chaque nombre.

Indice 2

Vérifiez ensuite chaque p tel que p + 2 ≤ limit.

Indice 3

Le premier couple est (3, 5), donc toute limite inférieure à 5 donne une liste vide.

Complexité attendue

temps O(limit log log limit), espace supplémentaire O(limit)

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.