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