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

Nombres amicaux

Listez tous les couples de nombres amicaux dont les deux nombres ne dépassent pas une limite.

Ce que vous allez apprendre

  • Construire une table des sommes de diviseurs stricts pour tous les nombres jusqu'à une limite
  • Vérifier une condition de couple dans les deux sens
  • Éviter de lister un couple deux fois ou de lister des nombres parfaits

Problème

Notons s(n) la somme des diviseurs stricts de n (ses diviseurs autres que n lui-même). Deux nombres distincts a et b forment un couple de nombres amicaux quand s(a) = b et s(b) = a. Le plus petit couple est 220 et 284, car s(220) = 1 + 2 + 4 + 5 + 10 + 11 + 20 + 22 + 44 + 55 + 110 = 284 et s(284) = 1 + 2 + 4 + 71 + 142 = 220.

Implémentez amicable_pair(limit).

Calculer s(n) séparément pour chaque n jusqu'à limit est lent. Un crible fonctionne mieux : pour chaque d, ajoutez d à chaque multiple de d supérieur à d.

Entrée

limit : la plus grande valeur autorisée pour chacun des deux nombres d'un couple.

Sortie

Renvoyez une liste de couples [a, b] avec a < b ≤ limit, triés par a croissant. Un couple n'est retenu que si ses deux nombres sont au plus égaux à limit. Les nombres parfaits (pour lesquels s(n) = n) ne forment pas de couple. S'il n'y en a aucun, renvoyez une liste vide.

Contraintes

1 ≤ limit ≤ 200 000

Exemples

Exemple 1
Entrée :
limit = 1500

Sortie attendue :
expected = [
    [220, 284],
    [1184, 1210]
]
Entrée :
long long limit = 1500;

Sortie attendue :
std::vector<std::vector<long long>> expected = {
    {220, 284},
    {1184, 1210}
};
Entrée :
long limit = 1500;

Sortie attendue :
long[][] expected = new long[][] {
    new long[] {220, 284},
    new long[] {1184, 1210}
};

Explication

s(220) = 284 et s(284) = 220, ainsi que s(1184) = 1210 et s(1210) = 1184. Les deux couples tiennent sous 1500 : [[220, 284], [1184, 1210]].

Exemple 2
Entrée :
limit = 250

Sortie attendue :
expected = []
Entrée :
long long limit = 250;

Sortie attendue :
std::vector<std::vector<long long>> expected = {};
Entrée :
long limit = 250;

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

Explication

220 ne dépasse pas 250, mais son partenaire 284 si, donc aucun couple ne convient : [].

Comment l'aborder

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

Indice 1

Pour chaque d de 1 à limit / 2, ajoutez d aux sommes de 2d, 3d, 4d, et ainsi de suite.

Indice 2

Pour chaque a, notez b la somme de ses diviseurs et vérifiez que b est dans l'intervalle et que la somme des diviseurs de b vaut a.

Indice 3

Exiger a < b permet de lister chaque couple une seule fois et d'écarter les nombres parfaits.

Complexité attendue

temps O(limit 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.