Somme des diviseurs propres
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:
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 :D
