NOMBRE_PREMIER
dom_ponge
Messages postés
47
Date d'inscription
mardi 1 juin 2004
Statut
Membre
Dernière intervention
17 septembre 2006
-
13 juil. 2006 à 22:44
coucou747 Messages postés 12303 Date d'inscription mardi 10 février 2004 Statut Membre Dernière intervention 30 juillet 2012 - 18 juil. 2006 à 13:19
coucou747 Messages postés 12303 Date d'inscription mardi 10 février 2004 Statut Membre Dernière intervention 30 juillet 2012 - 18 juil. 2006 à 13:19
Cette discussion concerne un article du site. Pour la consulter dans son contexte d'origine, cliquez sur le lien ci-dessous.
https://codes-sources.commentcamarche.net/source/38553-nombre-premier
https://codes-sources.commentcamarche.net/source/38553-nombre-premier
18 juil. 2006 à 13:19
17 juil. 2006 à 13:24
Une autre optimisation intéressante, plutot que d'aller de 2 en 2, pour des grands nombres, ca peut être intéressant de faire des sauts réguliers avec les écarts des premiers nombres premiers. Quand on saute de 2 en 2 trois fois de suite, on est fatalement tombé sur un multiple de 3, ce qui est intrinsèquement idiot. Donc on peut comme ca s'éviter des dizaines de tests inutiles.. 'suffit de regarder ca de plus près ensuite :)
16 juil. 2006 à 23:53
Ps J'ai mis 5 par erreur. Malalam, STP, tu peux corriger?
16 juil. 2006 à 21:54
16 juil. 2006 à 16:38
c'est une mauvaise solution ça...
if($nb%$val===0){
ça c'est mieux et moins lent
15 juil. 2006 à 00:57
en fait c'est en for($a=$i*2;$a<=$limit;$a+=$i) qu'il faut remplacer ..
15 juil. 2006 à 00:56
15 juil. 2006 à 00:53
for($i=2;$i<=$square;$i+=2)
mais
for($i=3;$i<=$square;$i+=2)
mais les perfs restent egales ( y a trop peu de nombres premiers pour faire la difference ..)
15 juil. 2006 à 00:48
<?
$deb = microtime(true);
$limit=11150;
$square = sqrt($limit);
$tab = Array();
for($i=0;$i<=$limit;$i++)
$tab[$i] = true;
for($i=2;$i<=$square;$i+=2)
{
if($tab[$i])
{
for($a=$i;$a<=$square;$a+=$i)
$tab[$a] = false;
}
}
echo microtime(true) - $deb;
?>
mais il est pas encore optimisé au max .. j'ai encore un truc (a essayer) d'ameliorer ..
14 juil. 2006 à 20:02
pas la peine de réinventer la roue... cf php.net
gmp_prob_prime()
14 juil. 2006 à 18:43
Je vois que hélas vous n'avez pas fait de cours de spécialité math en terminal. En effet en cours d'arithméthique on découvre que pour voir si un nombre est premier, il suffit de calculer sa racine carré et si ce nombre ne possède pas de diviseur entre 2 et sa racine carré alors il est premier.
Pour calculer une racine carré il suffit d'utiliser l'algorithme de Newton qui est très souvent utilisé dans les solutions embarqués à petit puissance de calcul tels que les téléphones portables. je te laisse le soin de le trouver je ne l'ai pas sous la main.(c'est une suite ).
Bien joué stepibou pour le break, je ne savais pas non plus que ça avait autant d'importance de mettre un break, joli coup d'optimisation ....
Cordialement,
Xeonarno
14 juil. 2006 à 17:41
14 juil. 2006 à 01:40
Chez moi ton code : 14.76s
celui d'en dessous sans le break : 12.57s
celui la : 1.54s
$nombres=array(2,3);
$nb=4;
$limit=11150;
while($nb<=$limit){
foreach($nombres as $val){
if(gettype($nb/$val) == 'integer'){
$nbpremier=false;
break;
}
}
if($nbpremier==true)
$nombres[]=$nb;
$nbpremier=true;
$nb++;
}
Voila presque 10 fois plus rapide,
On voit ici l'importance du break!
on peut encore améliorer,... a vous.
;)
13 juil. 2006 à 23:23
- 5/10
13 juil. 2006 à 22:44
Mais pour rajouté de la rapidité tu pourrai regardé si c'est un nombre pair(sauf pour le nombre 2) et si c'est ce l'est tu ne fait pas tout les calculs pour, sa le rendra 2 fois plus rapide!
Pour l'effort je donne 8.