Somme des diviseurs propres

**Neitsa** · 10/02/2007, 17h31

Bonjour à tous,

J'essaye de résoudre le problème situé à cette adresse (c'est un jeu de programmation / algorithmie) : http://www.spoj.pl/problems/DIVSUM/

Il s'agit de faire la somme des diviseurs "propres" (proper divisors) sachant que le diviseur propre d'un nombre naturel est un diviseur strictement inférieur à ce nombre. Par exemple :

20 a 5 diviseurs propres : 1, 2, 4, 5, 10, et la somme de ces diviseurs est : 1 + 2 + 4 + 5 + 10 = 22.

Le problème c'est que j'obtiens constamment un "Time exceed" lors du jugement, ce qui indique que mon programme ne va pas assez vite...

Je pense que mon algo est trop "naïf" mais je ne sais pas quoi faire pour aller plus vite...

Comme l'indique le problème, le temps limite est de 3 seconde avec 200 000 nombres en entrée et avec chaque nombre n tel que (1 <= n <= 500000).

Voilà, mon code :

Code C :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
 
#include <stdio.h>
#include <stdlib.h>
 
int main()
{
    int TestCases = 0, i = 0, x = 0;
    int num = 0, divisorSum = 0, bound = 0;
 
	scanf("%d", &TestCases);
 
	for (i = 0; i < TestCases; i++)
	{
	    scanf("%d", &num);
 
	    divisorSum = 0;
 
        if (num % 2 == 0)
            bound = num / 2;
        else
            bound = num / 3;
 
        for (x = 1; x <= bound; x++)
        {
            if (num % x == 0)
            {
                divisorSum += x;
            }
        }
        printf("%d\n", divisorSum);
	}
 
	return 0;
}

Que puis-je faire pour aller plus vite ?

Je vous remercie

**poof65** · 10/02/2007, 17h52

Tu peux essayer de faire une boucle de 2 à racine(n) puis dès que tu trouve un diviseur a, tu ajoute a puis n/a.

**PRomu@ld** · 10/02/2007, 18h22

En fait, tester les diviseurs jusqu'à racine de n est une bonne idée.

Ensuite, si tu veux aller plus vite, il va falloir ruser. En regardant les résultats des meilleurs, je vois que le premier à un temps d'éxécution assez petit ... 0. A mon avis, il y a eu un précalcul au moment de la compilation (méta-programmation c++).

J'aurai bien testé le calcul en utilisant la décomposition en facteurs premiers :

http://perso.orange.fr/yoda.guillaum...e.htm#theoreme

La formule me parait sympa mais je ne sais pas si ça va être plus rapide.

**Neitsa** · 10/02/2007, 19h22

Bonsoir,

Merci pour vos réponses

Effectivement, tester jusqu'à sqrt(n) était la solution !

J'avais quand même "bad answer" après avoir soumis ma solution, mais j'étais sûr que c'était la bonne après avoir testé plusieurs cas...

Après plusieurs longues minutes, je me suis aperçu qu'un cas spécial existait : la réponse à l'input "1" était forcément "0" (et non pas "1" comme mon algo me sortait..) !

Ceci dit, le problème est résolu, merci beaucoup à vous deux pour votre aide

**Zavonen** · 11/02/2007, 10h08

C'est l'algo classique pour déterminer les nombres dits "parfaits".
En fait les diviseurs se trouvent DEUX par DEUX et non un par un, et il suffit de s'arrêter à la racine du nombre, puis de faire un dernier test pour savoir si on a affaire à un carré parfait.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <stdio.h>
#include <stdlib.h>
 
int somme_div_propres (int n)
{ int i;
 int s;
  for (i=2, s=1; i*i<n; i++)
  //On ajoute deux par deux
  if (!(n%i)) s=s+i+n/i;
  // test du carré parfait
  if (n==i*i) n+=i; //si oui  on ajoute une seule fois
  return s;
}
 
 
int main()
{
	int test;
	printf("Donner un nombre entier ");
	scanf("%d", &test);
	printf ("La somme de ses diviseurs propres est:%d\n",somme_div_propres(test));
	return 0;
}

**jobherzt** · 12/02/2007, 10h31

dans le forum java ya eu une discussion dans le meme genre il n'y a as trop longtemps, j'avais donné un pseudo code naif mais pas trop :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
 
resultat <- []
 
factorise(N, depart)
 
//on traite le cas de 2 a part pour pouvoir ensuite avancer par pas de 2
si depart == 2
  tant que 2 divise N
    resultat[] <- 2
    N=N/2
  fin tant que
  factorise(N,3) // on recurse
sinon
  i<-depart
  tant que i ne divise pas N et i <= sqrt(N)+1// on cherche un diviseur
    i<-i+2
  fin tant que
  //si on en a trouvé un
  si i <= sqrt(N)+1
    tant que i divise N // on divise autant de fois que possible
      resultat[] <- i
      N=N/i
    fin tant que
    factorise(N, i+2) // on recurse
  sinon // c'est que N est premier, il n'y a plus de diviseurs
    resultat[] <- N // notre N est donc le dernier diviseur de notre nb de depart
  fin si
fin fonction

si tu veux un truc plus rapide mais pas trop technique nn plus, regarde l'algorithme de pollard de factorisation des entiers..