Problème
Un nombre est abondant lorsque la somme de ses diviseurs stricts (tous ses diviseurs sauf lui-même) le dépasse. Le plus petit est 12 : 1 + 2 + 3 + 4 + 6 = 16. Certains nombres s'écrivent comme la somme de deux nombres abondants (on peut prendre deux fois le même, comme dans 24 = 12 + 12), d'autres non. Additionnez tous les entiers strictement positifs de 1 à limit qui ne le peuvent pas.
Implémentez non_abundant_sums(limit).
Calculez d'un coup les sommes de diviseurs de tous les nombres à l'aide d'un crible, listez les nombres abondants, puis marquez toutes les sommes de deux d'entre eux qui ne dépassent pas la limite.
Entrée
limit : le plus grand nombre à examiner.
Sortie
Renvoyez la somme de tous les n tels que 1 ≤ n ≤ limit qui ne sont pas la somme de deux nombres abondants.
Contraintes
1 ≤ limit ≤ 10 000
Exemples
Entrée :
limit = 23
Sortie attendue :
expected = 276
Entrée :
long long limit = 23;
Sortie attendue :
long long expected = 276;
Entrée :
long limit = 23;
Sortie attendue :
long expected = 276;
Explication
Aucune somme de deux nombres abondants ne vaut 23 ou moins, donc tous les nombres comptent : 1 + 2 + ... + 23 = 276.
Entrée :
limit = 30
Sortie attendue :
expected = 411
Entrée :
long long limit = 30;
Sortie attendue :
long long expected = 411;
Entrée :
long limit = 30;
Sortie attendue :
long expected = 411;
Explication
24 = 12 + 12 et 30 = 12 + 18 sont exclus, donc la réponse est 465 − 24 − 30 = 411.
Comment l'aborder
Essayez d'abord seul, puis ouvrez les indices un par un.
Indice 1
Pour chaque i, ajoutez i à la somme des diviseurs de 2i, 3i, 4i, ...
Indice 2
Rassemblez les nombres abondants dans l'ordre croissant.
Indice 3
Pour chaque paire a ≤ b, arrêtez la boucle intérieure dès que a + b dépasse la limite.
Complexité attendue
temps O(limit log limit + A²) pour A nombres abondants, espace supplémentaire O(limit)
Références
Ce défi a été adapté pour CodeUtility. Suivez l'énoncé et les contraintes ci-dessus.