Project Euler : solution au problème 23, en Python

Un dernier pour aujourd'hui, vu que je ne serai sûrement pas vraiment généreux en code cette semaine, ni la semaine prochaine. Disons que je prends un peu d'avance.

Le problème 23 est une question de nombres abondants. Connaissant la somme des diviseurs propres d'un nombre, on dit que ce nombre est déficient si cette somme est inférieure à lui-même (c'est le cas du nombre 10), parfait si cette somme lui est égale (28 l'est), abondant si elle est supérieure à lui-même (12 est abondant).

Il est un fait établi que tous les nombres supérieurs à 28123 peuvent être écrits comme la somme de deux nombre abondants. Les entiers qui ne sont pas exprimables comme somme de deux abondants forment donc un ensemble fini. On en demande la somme.

#! /usr/bin/env python

# 2009/04/06 - euler023.py
# Solution au Probleme 23 de Project Euler
# http://projecteuler.net/index.php?section=problems&id=23
# Jean Karim Bockstael - jkb@jkbockstael.be

def getproperdivisors(num):
    res = []
    for i in range(1, num / 2 + 1):
        if (num % i == 0):
            res.append(i)
    return res

def sumofproperdivisors(num):
    return sum(getproperdivisors(num))

def isabundant(num):
    return (sumofproperdivisors(num) > num)

def getabundantnumbers(lim):
    res = []
    for i in range(1, lim + 1):
        if isabundant(i):
            res.append(i)
    return res

def issumofabundants(num, abundants):
    res = False
    for i in abundants:
        if ((num - i) in abundants):
            res = True
            break
    return res

def euler23(lim):
    abundants = getabundantnumbers(lim)
    res = []
    for i in range(1, lim + 1):
        if not (issumofabundants(i, abundants)):
            res.append(i)
    return sum(res)

print euler23(28123)

cc-by-nc | code (python) | project euler

<<< Exercices de Michel Couprie : solutions aux séries 1 et 2, en Python (2009-04-16) | Project Euler : solution au problème 22, en Python (2009-04-06) >>>