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

Sommes non abondantes

Additionner les nombres, jusqu'à une limite, qui ne s'écrivent pas comme la somme de deux nombres abondants.

Ce que vous allez apprendre

  • Calculer avec un crible les sommes de diviseurs sur tout un intervalle
  • Marquer les sommes atteignables dans un tableau de booléens
  • Interrompre une double boucle dès que les sommes dépassent la limite

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

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

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

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.