Discussion :

[bibi4537]

Bonjour à tous,

Je cherche à optimiser mon code pour un exercice en ligne. (sur le site www.codewars.com)
Voici le sujet:

Divisors of 42 are : 1, 2, 3, 6, 7, 14, 21, 42. These divisors squared are: 1, 4, 9, 36, 49, 196, 441, 1764. The sum of the squared divisors is 2500 which is 50 * 50, a square!

Given two integers m, n (1 <= m <= n) we want to find all integers between m and n whose sum of squared divisors is itself a square. 42 is such a number.

The result will be an array of arrays(in C an array of Pair), each subarray having two elements, first the number whose squared divisors is a square and then the sum of the squared divisors.

#Examples:

list_squared(1, 250) --> [[1, 1], [42, 2500], [246, 84100]]
list_squared(42, 250) --> [[42, 2500], [246, 84100]]

Et voici le code que j'ai pour le moment:

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
 
<?php
function listSquared($m, $n) {
    $response = [];
    //boucle principale de $m à $n
    for ($k=$m;$k<=$n;$k++) {
        //calcul de la somme des diviseurs au carré
        $sumSquareDiv = 0;
        for($j=1;$j<=$k;$j++) {
            if ($k%$j === 0) {
                $sumSquareDiv += $j**2;
            }
        }
        //si la racine du diviseur est un nombre entier on ajoute
        //$k et $sumSquareDiv à la réponse
        $rac = sqrt($sumSquareDiv);
        if(strpos($rac, '.') === false) {
            $element = array($k, $sumSquareDiv);
            $response[] = $element;
        }
    }
    //on retourne la réponse sous forme d'un tableau de tableaux à 2 entrées
    return($response);
}

Ce code fonctionne, mais lorsque je valide ce dernier sur ma plateforme d'exercice j'ai une erreur me disant que le code met trop de temps à s'executer.

Je cherche donc à optimiser mon code, mais je ne vois pas comment faire.

Si quelqu'un à une idée je suis preneur.

Merci à tous.

[rawsrc]

Salut,

bon généralement je n'aime pas faire les devoirs des autres, m'enfin aujourd'hui c'est ton jour de chance

Voici, ce que j'aurais proposé :

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
29
30
31
function list_squared($m, $n)
{
    $sum_square = function($p) {
        $total = ($p === 1) ? 1 : 1 + $p * $p;
        for ($i = 2; $i * $i <= $p; ++$i) {
            if ($p % $i === 0) {
                $total += $i * $i;
                if ($i * $i !== $p) {
                    $total += ($p / $i) * ($p / $i);
                }
            }
        }
 
        return $total;
    };
 
    $data = [];
 
    for ($i = $m; $i <= $n; ++$i) {
        $sum  = $sum_square($i);
        $sqrt = (int)sqrt($sum);
        if (($sqrt * $sqrt) === $sum) {
            $data[] = [$i, $sum];
        }
    }
 
    return $data;
}
 
$list_a = list_squared(1, 250);     // [[1, 1], [42, 2500], [246, 84100]]
$list_b = list_squared(42, 250);    // [[42, 2500], [246, 84100]]

Allez bonne continuation
Dis moi si je suis reçu

[bibi4537]

Salut à toi rawsrc,

et bien sache que tu es reçu

Ton code passe en environ 2.5s lors des test alors que le miens était recalé car il mettait plus de 12s!!!

Tu as donc largement optimisé mon code.

Encore merci pour ton aide et ta réactivité.

[Tsilefy]

Si tu veux grignoter quelques microsecondes de moins (mais la différence ne sera pas aussi flagrante qu'entre ta version et celle de rawsrc qui est stupéfiante), tu peux remplacer ses boucles for par do/while.

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
function list_squared_do_while($m, $n) {
	$sum_square = function($p) {
		$total = ($p === 1) ? 1 : 1 + $p * $p;
		$i = 2;
		do {
			if ($p % $i === 0) {
				$total += $i * $i;
				if ($i * $i !== $p) {
					$total += ($p / $i) * ($p / $i);
				}
			}
		} while($i * $i <= $p && ++$i);
 
		return $total;
	};
 
	$data = [];
 
	do {
		$sum  = $sum_square($m);
		$sqrt = (int)sqrt($sum);
		if (($sqrt * $sqrt) === $sum) {
			$data[] = [$m, $sum];
		}
	} while($m < $n && $m++);
 
	return $data;
}

Sur ma machine de test j'ai une différence d'environ 18%.

[Tsilefy]

Et il faudrait voir ce que ça donne avec goto :-D