Bonjour,

Encore moi et mes exos !

Je vous propose aujourd'hui (si vous voulez bien) de résoudre l'exercice 21 du Projet Euler :

On dit que deux nombres sont amicaux lorsque la somme des diviseurs de nomre1 est égale a nombre2 et que la somme des diviseurs de nomre2 est égale a nombre1.

Exemple : 220 et 284

• diviseurs de 220 : 1, 2, 4, 5, 10, 11, 20, 22, 44, 55 et 110 = 284
• diviseurs de 284 : 1, 2, 4, 71 et 142 = 220

Trouver la somme de tous les nombres amicaux en dessous de 10 000.

Méthode

Citation : Wikipédia

Il n'existe pas de formule ou méthode connue pour déterminer les nombres amicaux...

Nous allons donc devoir utiliser la force brute.


Eh bien, je me propose de vous démontrer qu'un brute force soigneusement réfléchi est nettement plus efficace. Mais je vous laisse d'abord proposer vos idées.

Il y a deux parties a coder :

• une fonction qui calcule la somme des diviseurs d'un nombre.
• un algo qui cherche exhaustivement tous les nombres amicaux jusqu'à une borne donnée.

Les algorithmes des deux parties devraient être optimisées pour être les plus rapides possible.

Allez, bon code !

Facile!

Je dois dire que je n'ai jamais résolu un problème d'algorithmique de ce niveau aussi vite.
Merci à toi, ça me fait un de plus sur leur site

PS: Il faut préciser aussi que par exemple, pour 6 c'est: 1, 2 et 3; mais ça fais 6, il ne faut donc pas le compter.

Merci de ta participation.

Vraiment très bien ta solution, j'essayerai de faire mieux dans mon corrigé !

Lol, je ne vois vraiment pas comment améliorer la fonction, faut que tu me dises comment

Un peu comme ca ?


Ainsi tu ne fait plus que 100 tours de boucle pour 10000 au lieu de 5000 tours (50 fois moins)

Code : C

int trouveAmical(int n)
{
  int i, total = 1;
  
  for(i=2; i*i<n; i++)
  {
     if(n%i == 0)
        total += i + n/i;
  }
  if (i*i == n)
  {
     total += i;
  }
  
  return total;
}

J'ai pas compris pourquoi la condition d'arret de la boucle est i*i< n et pourquoi total += i + n/i;

Parce que les diviseurs d'un nombre vont par deux

lorsque i divise n, tu as un j qui divise n tel que n = i*j, ou encore n/i = j (avec j>=i)

donc il suffit de parcourir les i jusqu'a ce que tu depasses la racine carrée du nombre (donc que tu ai (j< i)

Ici je m'arrete avant la racine carrée pour pas compter deux fois si elle existe

On peut sans doute faire mieux en adaptant le crible d'eratosthène.

Oui, mais ca deviens plus compliqué, car il faut faire la somme des diviseurs, donc la liste des diviseurs premiers ne suffiront pas (il faudra, a partir de la liste des diviseurs premiers, obtenir tout les diviseurs, ce qui est possible, mais plus chiant )

Pour 100 000 (donc 10 fois plus que nécessaire, sinon c'est trop court), le code naïf de onunload met 51s, celui de Flooder met 1.141s et le mien 0.057s, sur mon ordinateur.

À noter que les deux algorithmes, ne se comportent pas exactement pareil : le mien ne prend en compte que les nombres amicaux dont le conjoint se trouve aussi dans l'intervalle [0..LEN-1]. On peut corriger ça facilement (en retombant sur la méthode naïve quand on sort de cet intervalle), mais en pratique j'ai fait sans et ça ne change pas le résultat final. C'est peut-être une propriété mathématique, mais on s'en fout.

Bonjour,

Quasiment tout a été dit je crois !

Je me contente donc de poster mon code (et je prends note de la solution de bluestorm) :

#include <stdio.h>


#define MAX 10000

/* options de compilation - permettent de 
   choisir le mode voulu */
#define FAST    1
#define MISE_EN_CACHE   1


#if FAST
/* algo "intelligent" - complexité en O(sqrt(n)) */
unsigned sum_divisors (unsigned n)
{
    unsigned i;
    /* tout nombre est divisible par 1 */
    unsigned sum = 1;
    /* tant que i < sqrt(n) */
    for (i=2; i*i<n; i++)
        if (!(n%i))
            sum += i+(n/i);
    /* si i == sqrt(n) */
    if (i*i == n)
        sum += i;
    return sum;
}
#else
/* algo naif - complexité en O(n/2)*/
unsigned sum_divisors (unsigned n)
{
    unsigned i, sum = 1;
    for (i=2; i<=n/2; i++)
        if (!(n%i))
            sum += i;
    return sum;
}
#endif

int main(void)
{
    unsigned n, f_n, sum = 0;
#if MISE_EN_CACHE
    static size_t sum_div[MAX+1];
    unsigned i;
    /* mise en cache des résultats - évite les recalculs.
    le gain est particulièrement intéressant lorsque la
    fonction sum_divisors() n'est pas optimisée */
    for (i=1; i<=MAX; i++)
    {
        sum_div[i] = sum_divisors(i);
    }
    /* recherche - on accède au tableau sum_div[]
    au lieu d'appeler la fonction sum_divisors() */
    for (n=1; n<=MAX; n++)
    {
        f_n = sum_div[n];
        if (f_n <= MAX)
        {
            if (sum_div[f_n] == n && f_n < n)
            {
                sum += n+f_n;
            }
        }
    }
#else
    /* recherche directe
    - plus d'appels a la fonction sum_divisors(),
    mais moins de consommation mémoire. */
    for (n=1; n<=MAX; n++)
    {
        f_n = sum_divisors(n);
        if (f_n <= MAX)
        {
            if (sum_divisors(f_n) == n && f_n > n)
            {
                sum += n+f_n;
            }
        }
    }
#endif
    printf("%u\n", sum);
    return 0;
}

Je ne sais pas comment ecrire ça comme algorithme , j'ai pas étudié ça :-/

S'il est possible , quelqu'un le refait just comme algorithme

Bonjour, @ZakariaAitrahou merci de créer votre propre sujet en fournissant à la communauté le code que vous avez écrit (en utilisant le bouton code  </> du forum.). 

Déterrage

Citation des règles générales du forum :

Avant de poster un message, vérifiez la date du sujet dans lequel vous comptiez intervenir.

Si le dernier message sur le sujet date de plus de deux mois, mieux vaut ne pas répondre.
En effet, le déterrage d'un sujet nuit au bon fonctionnement du forum, et l'informatique pouvant grandement changer en quelques mois il n'est donc que rarement pertinent de déterrer un vieux sujet.

Au lieu de déterrer un sujet il est préférable :

• soit de contacter directement le membre voulu par messagerie privée en cliquant sur son pseudonyme pour accéder à sa page profil, puis sur le lien "Ecrire un message"
• soit de créer un nouveau sujet décrivant votre propre contexte
• ne pas répondre à un déterrage et le signaler à la modération

Je ferme ce sujet. En cas de désaccord, me contacter par MP.

-
Edité par AbcAbc6 25 février 2020 à 15:37:31