FONCTION QUI VÉRIFIE SI L'ARGUMENT EST UN NOMBRE PREMIER
biboux
Messages postés16Date d'inscriptionlundi 14 juin 2004StatutMembreDernière intervention 9 août 2010
-
8 août 2010 à 12:14
florianf.
Messages postés3Date d'inscriptionvendredi 14 août 2015StatutMembreDernière intervention16 août 2015
-
16 août 2015 à 00:41
Cette discussion concerne un article du site. Pour la consulter dans son contexte d'origine, cliquez sur le lien ci-dessous.
florianf.
Messages postés3Date d'inscriptionvendredi 14 août 2015StatutMembreDernière intervention16 août 2015 16 août 2015 à 00:41
La fonction dit que 0 et 1 sont premiers et 2 ne l'est pas. C'est le contraire.
La fonction dit que 9 n'est pas premier parce que le test sur $sqrt est fait avec === et pas ==.
florianf.
Messages postés3Date d'inscriptionvendredi 14 août 2015StatutMembreDernière intervention16 août 2015 16 août 2015 à 00:33
sauf que il y a un return avant le break. Le break n'est jamais exécuté.
kertimanoff
Messages postés75Date d'inscriptionsamedi 3 décembre 2005StatutMembreDernière intervention30 juin 2013 19 août 2010 à 11:59
en tout cas merci a tous pour ce moment de rêve que j'ai passé a lire les commentaires de cette source
lynxtyle
Messages postés79Date d'inscriptionsamedi 25 septembre 2004StatutMembreDernière intervention31 octobre 20112 10 août 2010 à 15:16
DARKELDA j'apprécis que t'ais pris en compte nos remarques :)
alors petit rajout à faire histoire de ne pas perdre du précieux temps de calcul : il faut rajouter une condition avant la boucle for (j'ai fait la même erreur dans mon exemple que j'ai rectifié dans mon dernier commentaire) car il ne sert à rien de rentrer dans la boucle for si $_nombre est pair ou un carré...
je te conseil donc de rassembler les conditions précédente dans un if(condition1 || condition2) suivi d'un else{for...
voilà c'est une petite optimisation non négligable pour un benchmark future ;)
en tout cas merci pour cette contribution et n'hésite pas à venir poster sur Codes-Sources : une source est toujours améliorable et tu pourras ainsi apprendre beaucoup de petites choses :-)
lynxtyle
Messages postés79Date d'inscriptionsamedi 25 septembre 2004StatutMembreDernière intervention31 octobre 20112 9 août 2010 à 17:29
j'ai oublié un "else" avant "for($i = 3; $i < $sqrt; $i=$i+2)" afin d'éviter de rentrer dans la boucle pour rien si is_int($sqrt) ou is_int($_nombre/2) et gagner du temps de calcul (beaucoup de temps d'ailleur)
voilou amusez vous bien
lynxtyle
Messages postés79Date d'inscriptionsamedi 25 septembre 2004StatutMembreDernière intervention31 octobre 20112 9 août 2010 à 16:21
DARKELDA quelques soit la source elle n'a pas vraiment d'intéret aussi bien du point de vu performance (mais là on a bien compris que c'était pas ton but) ni d'un point de vu pédagogique car tu ne considère pas les limites de ton système...
pour ma part le fait que tu ne te rends même pas compte que ta fonction retournera une valeur fausse si tu dépasse le PHP_INT_MAX (cf ton screen exemple) est une faute impardonnable...
pour ma part je suis pour le retrait de cette source si l'auteur ne fait pas un effort de réflexion et correction sur celle-ci (au minimum reprends ma fonction que tu réécris à ta façon ça ne me gêne pas...)
enfin tu comprendras peut être mieux la grosse erreur que je te reproche comme ça :
en php le $_nombre est un int signé tant que tu rentre un nombre au format int inférieur à PHP_INT_MAX, si tu dépasse PHP_INT_MAX le nombre est alors enregistré en float (exemple : $_nombre=2038313198765657683 sera enregistré en valeur approchée float égale à 2.0E19 sur une machine 32bits), au début de ta fonction tu fais if(is_int($_nombre)){...}else{return false} ce qui retournera false pour toute valeur suppérieur à PHP_INT_MAX et donc sur un serveur 32bits 32416190071 sera retourné non premier alors qu'il l'est belle et bien...
de plus tu es fière de ton benchmark sur tes temps de calcul (sans effectuer d'optimisation) mais sache qu'ils sont totalement faux : 4, 7 et 31 sont plus que rapide à calculer... et ton 999999999999992 lui n'est pas du tout calculté car considéré comme float... donc oui ton code et très rapide mais totalement faux car pour 32416190071 il sera aussi très rapide mais donnera une réponse erroné...
PS : pour la compréhention : dans le code j'ai "if(is_int($_nombre) && $_nombre>1)" car comme indiqué le $_nombre est un int signed... j'exclus donc tout ce qui se trouve <1 afin de ne pas rentrer dans la boucle pour rien en cas de nombre négatif et j'exclus au passage les 2 cas particulier de 0 et 1...
voilà cette exemple peut être utilisé comme support méthodologique pour un cours future ;-)
darkelda
Messages postés49Date d'inscriptionmardi 23 mars 2004StatutMembreDernière intervention16 mai 2012 9 août 2010 à 15:19
Ah oui juste pour info, depuis le départ, dans le zip il y a les 2 versions ...
lynxtyle
Messages postés79Date d'inscriptionsamedi 25 septembre 2004StatutMembreDernière intervention31 octobre 20112 9 août 2010 à 14:55
comme souvant mentionné : aucun interet d'utiliser PHP pour faire de la recherche sur les nombres premiers... mais cela peut avoir un interet méthodologique... sa source n'a pas cette interet car n'apporte rien et ne pose pas les limite d'utilisation...
sa fonction que j'ai recodé peut avoir un certain interet :
-logique mathématique (accélération basique de la recherche d'un nombre premier)
-méthodologie (le code répond au problème et ne présentera pas de bug car considère les cas particuliers)
enfin dans le cas où il y aurai utilité de savoir rapidement si un nombre est premier en php le plus simple et rapide c'est de le stocker dans un tableau (afin de pouvoir traiter de grand nombre), de d'abord vérifier s'il ne se termine pas par 0,2,4,5,6 ou 8 puis de comparer avec une liste de nombres premiers connus (la limite sera donc celle de la liste)
avec cette méthodologie pour accélérer la recherche (pour ne pas parcourir toute la liste) il suffit de comparer le nombre avec juste ce de la même longueur (il y a plein de sources qui traitent ce sujet... cf les tableau de char)
sinon passez votre chemin du php car il n'est pas optimisé pour faire de la recherche mathématique...
pmcoste
Messages postés72Date d'inscriptionmercredi 7 février 2007StatutMembreDernière intervention25 juillet 20131 9 août 2010 à 14:30
Bonjour,
Je ne voudrais pas rajouter mon grain de sel.
Mais dans la source, l'auteur nous donne un fabuleux exemple : Exécuter 7 fois (test sur 7 chiffres) la même procédure !
En effet, on calcule une fois au départ le tableau des nombres premiers, et ensuite, il n'y a plus qu'à récupérer son indice.
lynxtyle
Messages postés79Date d'inscriptionsamedi 25 septembre 2004StatutMembreDernière intervention31 octobre 20112 9 août 2010 à 13:28
DARKELDA je trouve vraiment dommage ta réaction vis à vis des remarques constructives de BIBOUX et OPTITECH car ils te suggère d'excellente solution d'optimisation de ton code...
pour ma part je considère ta source de départ inutile car il n'y a pas vraiment d'interet de vérifier un nombre premier en php surtout avec la limitation de ta variable... et d'un point de vu méthodologie même si ta source est propre elle m'apporte rien de spécial ni d'un point de vu du codage ni d'un point de vu mathématique... mais elle pourrait devenir interessante dans le cadre d'une recherche de son optimisation et il y aurait beaucoup de possibilité dans ce cas :
porter des algorithmes d'optimisations qui foisonnent en programmation C (ça serai assé original et permetterai de faire un petit benchmark entre langage compilé et langage interprété...)
une autre optique d'évolution de ce code qui pourrait le rendre très interessant serait d'enlever la limite imposé par la variable (au lieu de contenir la variable dans un int la contenir dans un tableau... les méthodes mathématiques du code seraient alors très interessantes...)
enfin c'est seulement mon avis...
@DARKELDA : ta capture est un très mauvais exemple car tu rentre même des nombres hors des limites de ta variable (même s'il t'a donné une réponse juste dans ce cas ça ne sera pas toujours le cas... si tu rentre un très grand premier il sera considéré comme non premier car traité comme une valeur approché de ta valeur sous la forme d'un float et donc est rejeté au moment ou tu is_int !!!)
je me suis amusé à réécrire ton code d'une autre façon pour qu'il soit interessant comme exemple méthodologique (je pose les limites d'exécution de la fonction et je l'optimise un minimum...)
function nombre_premier($_nombre)
{
if(is_int($_nombre) && $_nombre>1) //vérifie que c'est un int non signé et j'exclu 0 et 1 qui sont des cas spéciaux
{
$sqrt = sqrt($_nombre);
if (is_int($sqrt) || is_int($_nombre/2)) //vérifie que ça ne soit pas un carré ou un nombre pair
{
return false;
}
for($i = 3; $i < $sqrt; $i=$i+2) //vérifie qu'avec des diviseur impair (cf le wiki sur les nombres premiers)
{
if(is_int($_nombre/$i))
{
return false;
break;
}
}
return true;
}
else
{
echo "(Attention le resultat est faux : veuillez entrer un entier compris entre 2 et ".PHP_INT_MAX." !!!) "; //message d'information pour prévenir que ne nombre entré n'est pas dans les limites et que le résultat donné par cette fonction sera faux (car répondra toujours que ce n'est pas un nombre premier... ce qui sera souvant vrai^^) cette partie devrait faire l'objet d'une autre fonction (vérification du gabarie l'hors de l'entrée d'une valeur...)
}
}
j'ai rajouté une petite variable sympa : PHP_INT_MAX qui donnera la valeur maximal des int accepté par le système du serveur (qui peut avoir une valeur différente suivant que vous avez un 32bits, 64bits...)
pwoc
Messages postés38Date d'inscriptionsamedi 18 janvier 2003StatutMembreDernière intervention25 décembre 2007 9 août 2010 à 13:11
@LoveAngel1337:
----
"Dans mon cas, on détermine plus rapidement si un nombre N'est PAS premier. Donc dans le cas contraire, malheureusement, on parcoure la toute boucle !"
En effet, c'est le principe de tous les vérificateurs de primalité par boucle, le fait de rajouter la limite à la racine permet juste d'économiser quelques tours de boucle...
----
Si son objectif est vraiment de vérifier que le nombre n'est pas premier, il sortira de la boucle en même temps que nous ==> le calcul de la racine est inutile. (Bon, il faut un peu aller dans on sens aussi ^^)
pwoc
Messages postés38Date d'inscriptionsamedi 18 janvier 2003StatutMembreDernière intervention25 décembre 2007 9 août 2010 à 13:08
Bon, on va travailler par point aussi:
1) Il est vrai que si tu cherche à savoir si il n'est pas premier (mais alors, je te renverrais au titre de ta source), tu auras l'occurrence aussi vite, le calcul de la racine carrée en moins. Permets moi juste de te conseiller de passer tous les pairs, on gagne vraiment du temps.
2) Au final, chacun ses goûts.
3) Quel sens de l'humour, vraiment!
4) Si ton choix était de privilégier la sortie de boucle, tu ne dirais pas dans ton point (1) "Donc dans le cas contraire, malheureusement, on parcoure la toute boucle"
5) Non, d'où la question: Pouvez-vous me donner l'intérêt à poster ce code?
6) Ah ah super l'ironie encore... laisse moi quand même penser qu'il y a une part de vrai. La perfection ne doit pas venir du premier jet, et c'est bien la raison pour laquelle on a eu critiques à ton égard (critique dans le sens: Faire l'examen de (une œuvre d'art ou d'esprit) pour en faire ressortir les qualités et les défauts.(Le petit Robert 2010))
Optitech
Messages postés134Date d'inscriptionsamedi 19 octobre 2002StatutMembreDernière intervention 3 janvier 2009 9 août 2010 à 13:04
"1) Dans mon cas, on détermine plus rapidement si un nombre N'est PAS premier. Donc dans le cas contraire, malheureusement, on parcoure la toute boucle !"
Dans implémentation que je donne un je trouve un diviseur je fait un return, donc j'arrête la boucle, je ne vais jusque au bout.
LoveAngel1337
Messages postés2Date d'inscriptionlundi 1 décembre 2008StatutMembreDernière intervention 9 août 2010 9 août 2010 à 13:01
Rebonjour.
"Dans mon cas, on détermine plus rapidement si un nombre N'est PAS premier. Donc dans le cas contraire, malheureusement, on parcoure la toute boucle !"
En effet, c'est le principe de tous les vérificateurs de primalité par boucle, le fait de rajouter la limite à la racine permet juste d'économiser quelques tours de boucle...
"PAR CONSÉQUENT C'EST CETTE SYNTAXE QUE JE PRIVILÉGIES !"
Je vois pas de soucis sur ta syntaxe, à part le break après un return, mais ça...
Le fait que je fasse référence à tes expériences en python et ruby est juste là pour que tu te demande, avec le même algorithme, es-ce que dans un autre langage tu aurais fait le même code ? L'algorithme ne dépends pas du langage utilisé, et ce qu'on s'acharne à te faire comprendre, c'est que là, c'est ton algo qui n'est pas complet. Tu aurais aussi bien pu le faire en asm ou en brainfuck que ça n'aurais rien changé. A part l'état de notre cerveau. Même si, en passant, je préfère la syntaxe avec les {}. Mais ça, c'est une question de goût.
Non, je connais pas l'ironie. Mais justement, si tu la maitrise si bien, pourquoi tu prends comme excuse pour ne pas mettre le sqrt : "C'est une perte de temps processeur de vérifier la racine carrée (qui n'est pas forcément un nombre entier avec la fonction PHP)." ? Parce que faire racine du nombre tours de boucle en plus ne provoque pas de perte de temps processeur ? Intéressant.
Bah, si, tu as le droit de sortir de la boucle... C'est même ce qu'on essaye de t'aider à faire encore mieux ! ( Mais le return t'en fait déjà sortir, soit dit en passant )
Tu l'a dit toi même, c'est juste une réponse à "un exercice de méthodologie et d'algorithmie", pourquoi tu voudrais trouver des applications à ça ?
Après, y'a des personnes qui ont surement besoin de nombres premiers pour diverses raisons, et qui n'ont pas accès à des scripts extérieurs dans d'autres langages, ou à des super-calculateurs.
On est pas ici pour être des mathématiciens qui programment sur super-calculateurs, et c'est cet algo que tu as choisi, pas un de ces super-algorithmes.
Ce qu'on essaye de te faire comprendre, depuis déjà quelques personnes, c'est que tu peux améliorer ton programme, même si il n'a pas d'utilité. La perfection n'existe pas, peut être qu'elle existe encore moins en PHP que dans d'autres langages, mais là on ne parle même pas du langage !
Après, si tu ne veux pas comprendre que quand on te dit quelque chose, c'est pas pour te dire d'être parfait dès le début, mais pour te dire où sont les problèmes et améliorations possibles...
Optitech
Messages postés134Date d'inscriptionsamedi 19 octobre 2002StatutMembreDernière intervention 3 janvier 2009 9 août 2010 à 12:44
"5) Je réitère ma question : "Pouvez vous me donner 1 seul cas pratique de déterminer les nombres premiers dans du développement web ?"
Voici 2 idées :
- Explication est démonstration de RSA ou tout autre algo qui utilise des nombre premier (oui il faut bien vérifier que ce l'utilisateur saisi)
- Site d'énigmes sur le maths avec des énigmes sur les nombres premiers (oui on pourrait stoker le nombre premier dans un tableau statique, mais vive le dynamique)
darkelda
Messages postés49Date d'inscriptionmardi 23 mars 2004StatutMembreDernière intervention16 mai 2012 9 août 2010 à 12:28
J'adore quand on prend les propos des gens HORS CONTEXTE pour se justifier.
Tout d'abord :
1) Dans mon cas, on détermine plus rapidement si un nombre N'est PAS premier. Donc dans le cas contraire, malheureusement, on parcoure la toute boucle !
2)"Je ne code pas seulement qu'en PHP mais aussi en Python et en Ruby ... PAR CONSÉQUENT C'EST CETTE SYNTAXE QUE JE PRIVILÉGIES !" Hors contexte c'est plus simple à détourner
3) "Donne moi 1 et 1 seul cas pratique de déterminer les nombres premiers dans du développement web ??? Ah si ce code n'était là uniquement que pour répondre à un exercice de méthodologie et d'algorithmie ??? Mais NON !!! C'est très important de pouvoir gagner des microsecondes de calculs avec un serveur configuré pour tourner dans un mouchoir de poche connecté en 56k et placé à l'autre bout du globe !" L'ironie ??? Connais pas ?
4) Si c'est MON choix de privilégier la sortie de la boucle plutôt que son parcours ... Non je n'ai pas le droit ... On doit faire comme tout le monde, soit un bon petit mouton tu verras c'est toujours mieux ...
5) Je réitère ma question : "Pouvez vous me donner 1 seul cas pratique de déterminer les nombres premiers dans du développement web ?"
6) Ah oui il y a déjà des mathématiciens qui font de la recherche dans la détermination des nombres premiers avec des algorithmes plus solide et avec des super calculateurs. Ma fonction était sans prétention mais bon, on a pas le droit ! La perfection au premier jet !? J'y songes pour mon prochain code d'ailleurs !
pwoc
Messages postés38Date d'inscriptionsamedi 18 janvier 2003StatutMembreDernière intervention25 décembre 2007 9 août 2010 à 12:11
Re à tous,
Petite remarque pour Optitech, concernant ce bout de code:
$sqrt = sqrt($x);
if (is_int($sqrt)) // Sa racine carrée est entière ?
return (false);
is_int() se contente de vérifier si l'argument est de type entier... or sqrt() retourne a 'float' (d'après la documentation). Il faudrait faire l'essai, mais je pense que dans ce cas de figure is_int() retournera toujours 'false' et que le test ne sert à rien.
Par ailleurs, pour vérifier si un réel est bien entier, c'est encore une autre paire de manches (encore à cause de la précision des réel exprimé en binaire).
Bien à toi.
PwOc
pwoc
Messages postés38Date d'inscriptionsamedi 18 janvier 2003StatutMembreDernière intervention25 décembre 2007 9 août 2010 à 11:43
Bonjour à tous,
Et bien bien, quelles discutions autour d'un sujet qui devait être plié rapidement!
Je fais la même constatation que LoveAngel1337... quels nombres bien choisis pour un test qui veut prouver l'efficacité d'un algorithme.
Je te propose ci dessus de tester les deux fonctions (la tienne et celle proposée par Optitech (avec une petite correction)) pour des nombres allant de 1 à 300, et le tout sous forme de graphe. Chaque fonction est exécutée 10fois afin d'augmenter un peu le temps d'exécution (les nombres infiniment petits, c'est encore un autre problème en représentation de réel en binaire).
Les résultats reste tout de même assez parlant, et je te laisse le constater par toi même.
Sache finalement que mes propos (je dis "mes" mais je pense parler au nom de tous) visait simplement à t'indiquer quelques magies mathématiques qui furent découvertes bien avant nous, faciles à mettre en place dans ton code et permettant un vrai gain de temps... nous ne voulions en aucun cas détruire ton code, il ne fallait pas se sentir martyrisé.
Voilà, en espérant que tu puisse profiter pleinement des ressources offertes par Codes-Sources pour l'apprentissage et la découverte, je te souhiate de passer une bonne journée.
PwOc
LoveAngel1337
Messages postés2Date d'inscriptionlundi 1 décembre 2008StatutMembreDernière intervention 9 août 2010 9 août 2010 à 10:16
Bonjour à tous.
"Ah si ce code n'était là uniquement que pour répondre à un exercice de méthodologie et d'algorithmie ???"
Je pense que justement, si ce code n'est là que pour répondre à un exercice de méthodologie et d'algorithme, alors autant le faire correctement. J'ai eu à faire ces exercices il n'y a pas deux ans de cela, et on nous faisait utiliser systématiquement la racine du nombre comme limite de l'itération. Il y'a surement une raison.
De plus, tu dis que tu programme dans d'autres langages... Si tu parle ici de l'algorithme, le langage n'a pas d'importance. Quelque soit le langage, si tu fait le test de primalité par une boucle, tu utilisera la racine comme limite. Après, il y'a peut être des méthodes plus efficaces, mais pas avec un algorithme identique, ça rends la comparaison absurde.
Quant à ton test, il n'est pas pertinent. Tes nombres premiers sont 97 et 31. Tu as bien des grands nombres, mais ils sont soit pairs, donc divisible par 2 ( 1 tour de boucle ), ou 3 ( 2 tours de boucle ), ça ne donne pas vraiment un test concluant.
Si tu veux recommencer le test, en utilisant, au hasard, le nombre 15648977, par exemple. J'obtiens 13 secondes avec le sqrt, plus de 60 sans (je suis toujours en train d'attendre la fin d'exécution ), pour 10k itérations.
"C'est une perte de temps processeur de vérifier la racine carrée (qui n'est pas forcément un nombre entier avec la fonction PHP)."
"C'est très important de pouvoir gagner des microsecondes de calculs avec un serveur configuré pour tourner dans un mouchoir de poche connecté en 56k et placé à l'autre bout du globe !"
Je te laisse établir toi même la contradiction de tes propos.
Bonne journée.
cs_jeca
Messages postés341Date d'inscriptionmercredi 17 juillet 2002StatutMembreDernière intervention14 juillet 201114 9 août 2010 à 09:59
Bonjour,
Il manque un test :
si $_nombre == 2, c'est un nombre premier.
darkelda
Messages postés49Date d'inscriptionmardi 23 mars 2004StatutMembreDernière intervention16 mai 2012 9 août 2010 à 00:50
Il est vrai que vous n'êtes pas des donneurs de leçons... Toutes mes humbles excuses mes seigneurs !
Optitech
Messages postés134Date d'inscriptionsamedi 19 octobre 2002StatutMembreDernière intervention 3 janvier 2009 9 août 2010 à 00:42
+1 biboux
biboux
Messages postés16Date d'inscriptionlundi 14 juin 2004StatutMembreDernière intervention 9 août 2010 9 août 2010 à 00:21
Tu m'étonnes que certains partent, tu essaies de donner des leçons à tout le monde alors que chacune des remarques faites était pour t'aider à améliorer ton code.
Pour exemple, j'écris "Pour information : la fonction is_int ne marche que pour les nombres <= 2147483647" pour essayer d'être constructif(comme tu le demandes plus haut) et t'aider à trouver une source d'erreur possible dans ton code mais de ton côté tu le prends comme une critique.
C'est sûr que si tu penses qu'à chaque bout de code que tu vas poster ici tout le monde te diras 'ouah c'est génial! merci on attendait que toi' tu risques de tomber de bien haut. Les gens sont ici non seulement pour partager leur travail (ou une partie) avec les autres mais également pour s'entraider afin que chacun puisse progresser. Apparemment tu n'as pas besoin de l'aide de quiconque, j'en suis content pour toi (c'est sincère) et j'attends le prochain bouquin que tu sortiras qui nous permettra à tous de nous rendre compte à quel point nous sommes incultes (un peu moins sincère).
Sur ces bonnes paroles, bonne semaine tout de même à tout le monde !
darkelda
Messages postés49Date d'inscriptionmardi 23 mars 2004StatutMembreDernière intervention16 mai 2012 9 août 2010 à 00:09
"Pour information : la fonction is_int ne marche que pour les nombres <= 2147483647"
1) La précision se règle au niveau du fichier de configuration
2) Pour plus de performance, j'aurais fait ce code en C avec un bel algorithme très incompréhensible
3) Ah mais si je faisais la division par tout les nombres premier compris entre 1 et l'infini sachant que tout ces nombres serait stocké dans un tableau tout en combinant avec l'exécution d'un script shell côté serveur on ira encore plus vite !
4) Donne moi 1 et 1 seul cas pratique de déterminer les nombres premiers dans du développement web ??? Ah si ce code n'était là uniquement que pour répondre à un exercice de méthodologie et d'algorithmie ??? Mais NON !!! C'est très important de pouvoir gagner des microsecondes de calculs avec un serveur configuré pour tourner dans un mouchoir de poche connecté en 56k et placé à l'autre bout du globe !
5) Je comprends mieux pourquoi certains contributeurs sont partis de ce site ...
biboux
Messages postés16Date d'inscriptionlundi 14 juin 2004StatutMembreDernière intervention 9 août 2010 8 août 2010 à 23:55
Pour information : la fonction is_int ne marche que pour les nombres <= 2147483647
Pour les nombres au-dessus : plantage!!
J'espère que ma remarque est assez constructive pour toi !!
darkelda
Messages postés49Date d'inscriptionmardi 23 mars 2004StatutMembreDernière intervention16 mai 2012 8 août 2010 à 23:49
regardes les sources et la capture ...
Mon code fonction avec 15 aussi (voir code source encore une fois)
PS: Dans mon environnement de dev, le Max Time exec est 300 secondes ... et si je vous faire pour des grands nombres, JAMAIS je ne le ferai en PHP ... Il y a d'autres langages de programmation plus adapté !
Optitech
Messages postés134Date d'inscriptionsamedi 19 octobre 2002StatutMembreDernière intervention 3 janvier 2009 8 août 2010 à 23:23
J'ai oublier de dire 2038313183 est premier.
Optitech
Messages postés134Date d'inscriptionsamedi 19 octobre 2002StatutMembreDernière intervention 3 janvier 2009 8 août 2010 à 23:17
"Le break sert à quitter une boucle de type for(), foreach(), switch() ou while() donc elle sert !!! (Quand on la place au bon endroit je vous l'accorde)"
OUI, je sais que le break sert à qui une boucle ! Mais là il ne sert à rien. Test ceci !
Tu verra que le echo n'est pas exécute don le break aussi, car le return est débranchant (équivalant à un exit).
"avec un sqrt() avant de rentrer dans la boucle"
On parle pas en test avant la boucle mais en condition de boucle.
Sinon voici un code qui fonctionne (même avec 124803243)
function is_prime($x)
{
if (!is_int($x)) // C'est un entier ?
return (false);
if (is_int($x / 2)) // Il est divisible par 2 ?
return (false);
$sqrt = sqrt($x);
if (is_int($sqrt)) // Sa racine carrée est entière ?
return (false);
$sqrt = floor($sqrt);
for ($i 3 ; $i < $sqrt; $i $i + 2) // Alors en test de le diviser par tout les nombre impair jusqu'à ca racine.
if (is_int($x / $i))
return (false);
return (true);
}
PS : Ton code plante avec 15. Ton break est mal placé. En le supprimant le code devient juste. MAIS pour le nombre 2038313183 voilà le résultat de ton script : "Fatal error: Maximum execution time of 60 seconds exceeded" le code qui se situe juste au dessus met 0,0192 s a retourner le bon résultat.
PS2 : Pour test avec de gros nombre premier tu peux trouver de gros nombre premier sur http://www.bigprimes.net/
darkelda
Messages postés49Date d'inscriptionmardi 23 mars 2004StatutMembreDernière intervention16 mai 2012 8 août 2010 à 23:08
@agparchitecture : Merci pour ton intervention qui m'a permit au final de re-poster le code d'origine. Et surtout qui m'a permis de ne pas me laisser emporter par les critiques peu constructive et sans fondement. À tête reposée, on y voit toujours plus clair.
Pour les autres, j'ai modifié le test comparatif (voir capture et zip pour plus de détails) pour faire 10 000 itérations pour que les différences soient bien mises en évidence.
Si je n'avais pas fait appel à la fonction sqrt() et à l'instruction break, c'est que j'avais mes raisons. La preuve en image et dans le zip !
Cordialement.
darkelda
Messages postés49Date d'inscriptionmardi 23 mars 2004StatutMembreDernière intervention16 mai 2012 8 août 2010 à 22:32
J'ai changé les tests de performances pour les passer à 10 000 itérations pour que ce soit plus significatif ...
@agparchitecture : Pour 124803243 il y a bien un bug, je vais regarder pourquoi il ne détecte pas que celà n'est pas un nombre premier. Merci pour ta remarque. (enfin une qui est constructive)
agparchitecture
Messages postés88Date d'inscriptionjeudi 9 mars 2006StatutMembreDernière intervention 7 novembre 2010 8 août 2010 à 22:23
Si par définition un nombre entier est un nombre divisible uniquement par 1 et lui même, il me semble qu'il y a une erreur dans l'exemple et donc avec la fonction:
124803243 / 9 13867027 Ce qui en découle qu'il est également divisible par 3> 124803243 / 3 = 41601081
Si ma mémoire est bonne, il me semble que pour savoir si un chiffre est divisible par 3 est de vérifier que la somme des chiffres qui compose le nombre n'est pas divisible par 3.
Il apparait ici que 1+2+4+8+0+3+2+4+3 = 27 (divisible par 3).
Ou bien il y a quelque chose qui m'échappe dans la fonction.
darkelda
Messages postés49Date d'inscriptionmardi 23 mars 2004StatutMembreDernière intervention16 mai 2012 8 août 2010 à 22:03
Rien ne vaut qu'une image plutôt que de longue explication ... PLUS RAPIDE avec un sqrt() avant de rentrer dans la boucle. ENTIEREMENT D'ACCORD !!! On gagne en rapidité !
0.000299 seconde est plus petit que 0.000253 seconde bien entendu !
Tout est dans le zip ...
Le break sert à quitter une boucle de type for(), foreach(), switch() ou while() donc elle sert !!! (Quand on la place au bon endroit je vous l'accorde)
Je ne code pas seulement qu'en PHP mais aussi en Python et en Ruby ... Par conséquent c'est cette syntaxe que je privilégies ! Après si on sait pas lire ...
pwoc
Messages postés38Date d'inscriptionsamedi 18 janvier 2003StatutMembreDernière intervention25 décembre 2007 8 août 2010 à 15:31
Bonjour à tous,
J'irai également dans le sens de Biboux et Optitech. Il ne sert à rien de vérifier si le nombre "premier" est bien multiple de nombres supérieurs à la racine de celui-ci (on me suit ? :D). Niveau temps d'exécution, c'est un grand gain de temps en le sens qu'on laisse tomber bien plus de la moitié de éléments à vérifier (ex: si le nombre à vérifier est 97, on n'effectue la boucle que de 2 à 9,84 soit 9 et on sait que 97 est premier).
Autre optimisation possible: Tu continues de vérifier pour tous les nombres pairs... alors que tu sais déjà que le nombre n'était pas multiple de 2... La il s'agit de laisser tomber la moitié des vérifications.
Sinon le code est propre et bien commenté (même si côté syntaxique, la version {} proposée par php est plus lisible)
Bonne continuation
PwOc
Optitech
Messages postés134Date d'inscriptionsamedi 19 octobre 2002StatutMembreDernière intervention 3 janvier 2009 8 août 2010 à 14:12
"Ah oui, le "break" à la ligne 15 permet de qui la boucle pour ne pas continuer la vérification."
À la ligne juste avant ton break tu à un return. Or return est débranchant, cela signifie que ca quitte la fonction donc ton break n'est jamais éxécuté.
Je confirme ce que dit Biboux, ca ne sert à rien de test ton nombre avec des nombres qui sont au dessus de la racine. Tu divisera ton temps de réponse positive par 2.
Sinon
for (...):
// Code was deleted here
endfor;
ou
if (...):
// code was deleted here
endif;
C'est très moche et ilisible.
biboux
Messages postés16Date d'inscriptionlundi 14 juin 2004StatutMembreDernière intervention 9 août 2010 8 août 2010 à 13:25
Testes ma méthode et tu verras que tu y gagnes beaucoup sur des grands chiffres non premiers. Ce n'est pas gênant d'avoir un float car il ne sert que comme 'arret' de la boucle for. Tu peux même faire '$racine=floor(sqrt($nombre))' si tu veux avoir un entier(ça marche aussi)
darkelda
Messages postés49Date d'inscriptionmardi 23 mars 2004StatutMembreDernière intervention16 mai 2012 8 août 2010 à 13:12
Excuse moi pour mon caractère agressif. Je te remercies pour ton aide.
Mais la fonction sqrt() retourne un float et non un entier. Donc dans la plupart des cas, on sort du cadre des nombres entiers.
Concernant l'optimisation. On peut le faire que dans 1 seul sens, dans mon cas, on détermine plus rapidement si un nombre n'est pas premier. Donc dans le cas contraire, malheureusement, on parcoure la toute boucle.
biboux
Messages postés16Date d'inscriptionlundi 14 juin 2004StatutMembreDernière intervention 9 août 2010 8 août 2010 à 13:01
Pour mon 1er commentaire, j'ai dit qu'il était écrit 'entier' alors qu'il aurait dû y avoir 'premier'
Pour la suite, je n'ai pas parlé de pré-vérification! Je t'ai proposé une solution pouvant t'éviter la moitié des passages dans la boucle pour les nombres n'étant pas premiers.
Apparemment tu lis pas ce que j'écris, tant pis pour toi, je cherchais seulement a t'aider!
darkelda
Messages postés49Date d'inscriptionmardi 23 mars 2004StatutMembreDernière intervention16 mai 2012 8 août 2010 à 12:54
En fait même pas pour la pré-vérification.
Car en général, les entiers sont multiples de 2, 3 et 5 et comme ce sont les premiers à être vérifié dans la boucle. On sort très vite de cette dernière.
Donc non ! C'est une perte de temps processeur de vérifier la racine carrée (qui n'est pas forcément un nombre entier avec la fonction PHP).
darkelda
Messages postés49Date d'inscriptionmardi 23 mars 2004StatutMembreDernière intervention16 mai 2012 8 août 2010 à 12:45
Euh vérifies ton premier commentaire.
+1 pour la pré-vérification. Çà éviterai de rentrer dans la boucle, si il existe une racine mais si ce n'est pas le cas, la pré-vérification prends du temps processeur pour rien sur des nombres très grand.
biboux
Messages postés16Date d'inscriptionlundi 14 juin 2004StatutMembreDernière intervention 9 août 2010 8 août 2010 à 12:40
Pour ton information:
-quand j'ai regardé tout à l'heure, le titre était bien: "....nombre entier", d'où mon 1er commentaire
-pour le 2ème, rien à voir avec ton "break". Si le nombre n'est pas premier, ça t'evitera de parcourir les valeurs supérieures a la racine(car inutile). Cela améliorera vraiment les performances. Ne crois pas m'expliquer ce qu'est un nombre premier, je connais très bien!
Bonne journée a toi !
darkelda
Messages postés49Date d'inscriptionmardi 23 mars 2004StatutMembreDernière intervention16 mai 2012 8 août 2010 à 12:31
Ah oui, le "break" à la ligne 15 permet de qui la boucle pour ne pas continuer la vérification.
darkelda
Messages postés49Date d'inscriptionmardi 23 mars 2004StatutMembreDernière intervention16 mai 2012 8 août 2010 à 12:24
darkelda
Messages postés49Date d'inscriptionmardi 23 mars 2004StatutMembreDernière intervention16 mai 2012 8 août 2010 à 12:23
1) Je te rassure le titre est bon, c'est bien nombre PREMIER et nombre ENTIER !
2) Si je voulais gagner en performance pour déterminer un nombre ENTIER, j'utiliserai la fonction is_int() qui est hard codé et donc ma fonciton serait totalement obsolète puisque je réinvente la roue.
Pour information, un nombre PREMIER est un nombre qui n'est divisible que par 1 et par lui même
biboux
Messages postés16Date d'inscriptionlundi 14 juin 2004StatutMembreDernière intervention 9 août 2010 8 août 2010 à 12:14
Bonjour,
2 petits commentaires sur ta source:
-le titre n'est pas bon je pense('entier' au lieu de 'premier')
-si tu veux gagner énormément en performances, tu peux arrêter ta boucle à racine carrée de nombre(si le nombre est pas multiple d'un nombre en dessous, il sera forcément pas multiple d'un ombre au-dessus). Ainsi ça deviendra:
16 août 2015 à 00:41
La fonction dit que 9 n'est pas premier parce que le test sur $sqrt est fait avec === et pas ==.
16 août 2015 à 00:33
19 août 2010 à 11:59
10 août 2010 à 15:16
alors petit rajout à faire histoire de ne pas perdre du précieux temps de calcul : il faut rajouter une condition avant la boucle for (j'ai fait la même erreur dans mon exemple que j'ai rectifié dans mon dernier commentaire) car il ne sert à rien de rentrer dans la boucle for si $_nombre est pair ou un carré...
je te conseil donc de rassembler les conditions précédente dans un if(condition1 || condition2) suivi d'un else{for...
voilà c'est une petite optimisation non négligable pour un benchmark future ;)
en tout cas merci pour cette contribution et n'hésite pas à venir poster sur Codes-Sources : une source est toujours améliorable et tu pourras ainsi apprendre beaucoup de petites choses :-)
9 août 2010 à 17:29
voilou amusez vous bien
9 août 2010 à 16:21
pour ma part le fait que tu ne te rends même pas compte que ta fonction retournera une valeur fausse si tu dépasse le PHP_INT_MAX (cf ton screen exemple) est une faute impardonnable...
pour ma part je suis pour le retrait de cette source si l'auteur ne fait pas un effort de réflexion et correction sur celle-ci (au minimum reprends ma fonction que tu réécris à ta façon ça ne me gêne pas...)
enfin tu comprendras peut être mieux la grosse erreur que je te reproche comme ça :
en php le $_nombre est un int signé tant que tu rentre un nombre au format int inférieur à PHP_INT_MAX, si tu dépasse PHP_INT_MAX le nombre est alors enregistré en float (exemple : $_nombre=2038313198765657683 sera enregistré en valeur approchée float égale à 2.0E19 sur une machine 32bits), au début de ta fonction tu fais if(is_int($_nombre)){...}else{return false} ce qui retournera false pour toute valeur suppérieur à PHP_INT_MAX et donc sur un serveur 32bits 32416190071 sera retourné non premier alors qu'il l'est belle et bien...
de plus tu es fière de ton benchmark sur tes temps de calcul (sans effectuer d'optimisation) mais sache qu'ils sont totalement faux : 4, 7 et 31 sont plus que rapide à calculer... et ton 999999999999992 lui n'est pas du tout calculté car considéré comme float... donc oui ton code et très rapide mais totalement faux car pour 32416190071 il sera aussi très rapide mais donnera une réponse erroné...
pour ce qui veulent tester :
<?php
function nombre_premier($_nombre)
{
if(is_int($_nombre) && $_nombre>1)
{
$sqrt = sqrt($_nombre);
if (is_int($sqrt) || is_int($_nombre/2))
{
return false;
}
for($i = 3; $i < $sqrt; $i=$i+2)
{
if(is_int($_nombre/$i))
{
return false;
break;
}
}
return true;
}
else
{
echo "(Attention le resultat est faux : veuillez entrer un entier compris entre 2 et ".PHP_INT_MAX." !!!) ";
}
}
?>
<?php echo nombre_premier(4)? 'PREMIER' : 'PAS PREMIER'; ?>
<?php echo nombre_premier(7)? 'PREMIER' : 'PAS PREMIER';; ?>
<?php echo nombre_premier(11)? 'PREMIER' : 'PAS PREMIER';; ?>
<?php echo nombre_premier(23)? 'PREMIER' : 'PAS PREMIER';; ?>
<?php echo nombre_premier(24)? 'PREMIER' : 'PAS PREMIER';; ?>
<?php echo nombre_premier(31)? 'PREMIER' : 'PAS PREMIER';; ?>
<?php echo nombre_premier(179430059)? 'PREMIER' : 'PAS PREMIER';; ?>
<?php echo nombre_premier(32416190071)? 'PREMIER' : 'PAS PREMIER';; ?>
<?php echo nombre_premier(2038313183)? 'PREMIER' : 'PAS PREMIER';; ?>
<?php echo nombre_premier(-31)? 'PREMIER' : 'PAS PREMIER';; ?>
<?php echo nombre_premier(4.89)? 'PREMIER' : 'PAS PREMIER';; ?>
<?php echo nombre_premier(974365496326392643269543)? 'PREMIER' : 'PAS PREMIER';; ?>
PS : pour la compréhention : dans le code j'ai "if(is_int($_nombre) && $_nombre>1)" car comme indiqué le $_nombre est un int signed... j'exclus donc tout ce qui se trouve <1 afin de ne pas rentrer dans la boucle pour rien en cas de nombre négatif et j'exclus au passage les 2 cas particulier de 0 et 1...
voilà cette exemple peut être utilisé comme support méthodologique pour un cours future ;-)
9 août 2010 à 15:19
9 août 2010 à 14:55
sa fonction que j'ai recodé peut avoir un certain interet :
-logique mathématique (accélération basique de la recherche d'un nombre premier)
-méthodologie (le code répond au problème et ne présentera pas de bug car considère les cas particuliers)
enfin dans le cas où il y aurai utilité de savoir rapidement si un nombre est premier en php le plus simple et rapide c'est de le stocker dans un tableau (afin de pouvoir traiter de grand nombre), de d'abord vérifier s'il ne se termine pas par 0,2,4,5,6 ou 8 puis de comparer avec une liste de nombres premiers connus (la limite sera donc celle de la liste)
avec cette méthodologie pour accélérer la recherche (pour ne pas parcourir toute la liste) il suffit de comparer le nombre avec juste ce de la même longueur (il y a plein de sources qui traitent ce sujet... cf les tableau de char)
sinon passez votre chemin du php car il n'est pas optimisé pour faire de la recherche mathématique...
9 août 2010 à 14:30
Je ne voudrais pas rajouter mon grain de sel.
Mais dans la source, l'auteur nous donne un fabuleux exemple : Exécuter 7 fois (test sur 7 chiffres) la même procédure !
Il existe d'autres algorithmes qui à mon avis seraient plus rapide :
http://fr.wikipedia.org/wiki/Nombre_premier#Crible_d.27.C3.89ratosth.C3.A8ne_et_algorithme_par_essais_de_division
En effet, on calcule une fois au départ le tableau des nombres premiers, et ensuite, il n'y a plus qu'à récupérer son indice.
9 août 2010 à 13:28
pour ma part je considère ta source de départ inutile car il n'y a pas vraiment d'interet de vérifier un nombre premier en php surtout avec la limitation de ta variable... et d'un point de vu méthodologie même si ta source est propre elle m'apporte rien de spécial ni d'un point de vu du codage ni d'un point de vu mathématique... mais elle pourrait devenir interessante dans le cadre d'une recherche de son optimisation et il y aurait beaucoup de possibilité dans ce cas :
porter des algorithmes d'optimisations qui foisonnent en programmation C (ça serai assé original et permetterai de faire un petit benchmark entre langage compilé et langage interprété...)
une autre optique d'évolution de ce code qui pourrait le rendre très interessant serait d'enlever la limite imposé par la variable (au lieu de contenir la variable dans un int la contenir dans un tableau... les méthodes mathématiques du code seraient alors très interessantes...)
enfin c'est seulement mon avis...
@DARKELDA : ta capture est un très mauvais exemple car tu rentre même des nombres hors des limites de ta variable (même s'il t'a donné une réponse juste dans ce cas ça ne sera pas toujours le cas... si tu rentre un très grand premier il sera considéré comme non premier car traité comme une valeur approché de ta valeur sous la forme d'un float et donc est rejeté au moment ou tu is_int !!!)
je me suis amusé à réécrire ton code d'une autre façon pour qu'il soit interessant comme exemple méthodologique (je pose les limites d'exécution de la fonction et je l'optimise un minimum...)
function nombre_premier($_nombre)
{
if(is_int($_nombre) && $_nombre>1) //vérifie que c'est un int non signé et j'exclu 0 et 1 qui sont des cas spéciaux
{
$sqrt = sqrt($_nombre);
if (is_int($sqrt) || is_int($_nombre/2)) //vérifie que ça ne soit pas un carré ou un nombre pair
{
return false;
}
for($i = 3; $i < $sqrt; $i=$i+2) //vérifie qu'avec des diviseur impair (cf le wiki sur les nombres premiers)
{
if(is_int($_nombre/$i))
{
return false;
break;
}
}
return true;
}
else
{
echo "(Attention le resultat est faux : veuillez entrer un entier compris entre 2 et ".PHP_INT_MAX." !!!) "; //message d'information pour prévenir que ne nombre entré n'est pas dans les limites et que le résultat donné par cette fonction sera faux (car répondra toujours que ce n'est pas un nombre premier... ce qui sera souvant vrai^^) cette partie devrait faire l'objet d'une autre fonction (vérification du gabarie l'hors de l'entrée d'une valeur...)
}
}
j'ai rajouté une petite variable sympa : PHP_INT_MAX qui donnera la valeur maximal des int accepté par le système du serveur (qui peut avoir une valeur différente suivant que vous avez un 32bits, 64bits...)
9 août 2010 à 13:11
----
"Dans mon cas, on détermine plus rapidement si un nombre N'est PAS premier. Donc dans le cas contraire, malheureusement, on parcoure la toute boucle !"
En effet, c'est le principe de tous les vérificateurs de primalité par boucle, le fait de rajouter la limite à la racine permet juste d'économiser quelques tours de boucle...
----
Si son objectif est vraiment de vérifier que le nombre n'est pas premier, il sortira de la boucle en même temps que nous ==> le calcul de la racine est inutile. (Bon, il faut un peu aller dans on sens aussi ^^)
9 août 2010 à 13:08
1) Il est vrai que si tu cherche à savoir si il n'est pas premier (mais alors, je te renverrais au titre de ta source), tu auras l'occurrence aussi vite, le calcul de la racine carrée en moins. Permets moi juste de te conseiller de passer tous les pairs, on gagne vraiment du temps.
2) Au final, chacun ses goûts.
3) Quel sens de l'humour, vraiment!
4) Si ton choix était de privilégier la sortie de boucle, tu ne dirais pas dans ton point (1) "Donc dans le cas contraire, malheureusement, on parcoure la toute boucle"
5) Non, d'où la question: Pouvez-vous me donner l'intérêt à poster ce code?
6) Ah ah super l'ironie encore... laisse moi quand même penser qu'il y a une part de vrai. La perfection ne doit pas venir du premier jet, et c'est bien la raison pour laquelle on a eu critiques à ton égard (critique dans le sens: Faire l'examen de (une œuvre d'art ou d'esprit) pour en faire ressortir les qualités et les défauts.(Le petit Robert 2010))
9 août 2010 à 13:04
Dans implémentation que je donne un je trouve un diviseur je fait un return, donc j'arrête la boucle, je ne vais jusque au bout.
9 août 2010 à 13:01
"Dans mon cas, on détermine plus rapidement si un nombre N'est PAS premier. Donc dans le cas contraire, malheureusement, on parcoure la toute boucle !"
En effet, c'est le principe de tous les vérificateurs de primalité par boucle, le fait de rajouter la limite à la racine permet juste d'économiser quelques tours de boucle...
"PAR CONSÉQUENT C'EST CETTE SYNTAXE QUE JE PRIVILÉGIES !"
Je vois pas de soucis sur ta syntaxe, à part le break après un return, mais ça...
Le fait que je fasse référence à tes expériences en python et ruby est juste là pour que tu te demande, avec le même algorithme, es-ce que dans un autre langage tu aurais fait le même code ? L'algorithme ne dépends pas du langage utilisé, et ce qu'on s'acharne à te faire comprendre, c'est que là, c'est ton algo qui n'est pas complet. Tu aurais aussi bien pu le faire en asm ou en brainfuck que ça n'aurais rien changé. A part l'état de notre cerveau. Même si, en passant, je préfère la syntaxe avec les {}. Mais ça, c'est une question de goût.
Non, je connais pas l'ironie. Mais justement, si tu la maitrise si bien, pourquoi tu prends comme excuse pour ne pas mettre le sqrt : "C'est une perte de temps processeur de vérifier la racine carrée (qui n'est pas forcément un nombre entier avec la fonction PHP)." ? Parce que faire racine du nombre tours de boucle en plus ne provoque pas de perte de temps processeur ? Intéressant.
Bah, si, tu as le droit de sortir de la boucle... C'est même ce qu'on essaye de t'aider à faire encore mieux ! ( Mais le return t'en fait déjà sortir, soit dit en passant )
Tu l'a dit toi même, c'est juste une réponse à "un exercice de méthodologie et d'algorithmie", pourquoi tu voudrais trouver des applications à ça ?
Après, y'a des personnes qui ont surement besoin de nombres premiers pour diverses raisons, et qui n'ont pas accès à des scripts extérieurs dans d'autres langages, ou à des super-calculateurs.
On est pas ici pour être des mathématiciens qui programment sur super-calculateurs, et c'est cet algo que tu as choisi, pas un de ces super-algorithmes.
Ce qu'on essaye de te faire comprendre, depuis déjà quelques personnes, c'est que tu peux améliorer ton programme, même si il n'a pas d'utilité. La perfection n'existe pas, peut être qu'elle existe encore moins en PHP que dans d'autres langages, mais là on ne parle même pas du langage !
Après, si tu ne veux pas comprendre que quand on te dit quelque chose, c'est pas pour te dire d'être parfait dès le début, mais pour te dire où sont les problèmes et améliorations possibles...
9 août 2010 à 12:44
Voici 2 idées :
- Explication est démonstration de RSA ou tout autre algo qui utilise des nombre premier (oui il faut bien vérifier que ce l'utilisateur saisi)
- Site d'énigmes sur le maths avec des énigmes sur les nombres premiers (oui on pourrait stoker le nombre premier dans un tableau statique, mais vive le dynamique)
9 août 2010 à 12:28
Tout d'abord :
1) Dans mon cas, on détermine plus rapidement si un nombre N'est PAS premier. Donc dans le cas contraire, malheureusement, on parcoure la toute boucle !
2)"Je ne code pas seulement qu'en PHP mais aussi en Python et en Ruby ... PAR CONSÉQUENT C'EST CETTE SYNTAXE QUE JE PRIVILÉGIES !" Hors contexte c'est plus simple à détourner
3) "Donne moi 1 et 1 seul cas pratique de déterminer les nombres premiers dans du développement web ??? Ah si ce code n'était là uniquement que pour répondre à un exercice de méthodologie et d'algorithmie ??? Mais NON !!! C'est très important de pouvoir gagner des microsecondes de calculs avec un serveur configuré pour tourner dans un mouchoir de poche connecté en 56k et placé à l'autre bout du globe !" L'ironie ??? Connais pas ?
4) Si c'est MON choix de privilégier la sortie de la boucle plutôt que son parcours ... Non je n'ai pas le droit ... On doit faire comme tout le monde, soit un bon petit mouton tu verras c'est toujours mieux ...
5) Je réitère ma question : "Pouvez vous me donner 1 seul cas pratique de déterminer les nombres premiers dans du développement web ?"
6) Ah oui il y a déjà des mathématiciens qui font de la recherche dans la détermination des nombres premiers avec des algorithmes plus solide et avec des super calculateurs. Ma fonction était sans prétention mais bon, on a pas le droit ! La perfection au premier jet !? J'y songes pour mon prochain code d'ailleurs !
9 août 2010 à 12:11
Petite remarque pour Optitech, concernant ce bout de code:
$sqrt = sqrt($x);
if (is_int($sqrt)) // Sa racine carrée est entière ?
return (false);
is_int() se contente de vérifier si l'argument est de type entier... or sqrt() retourne a 'float' (d'après la documentation). Il faudrait faire l'essai, mais je pense que dans ce cas de figure is_int() retournera toujours 'false' et que le test ne sert à rien.
Par ailleurs, pour vérifier si un réel est bien entier, c'est encore une autre paire de manches (encore à cause de la précision des réel exprimé en binaire).
Bien à toi.
PwOc
9 août 2010 à 11:43
Et bien bien, quelles discutions autour d'un sujet qui devait être plié rapidement!
Je fais la même constatation que LoveAngel1337... quels nombres bien choisis pour un test qui veut prouver l'efficacité d'un algorithme.
Je te propose ci dessus de tester les deux fonctions (la tienne et celle proposée par Optitech (avec une petite correction)) pour des nombres allant de 1 à 300, et le tout sous forme de graphe. Chaque fonction est exécutée 10fois afin d'augmenter un peu le temps d'exécution (les nombres infiniment petits, c'est encore un autre problème en représentation de réel en binaire).
Les résultats reste tout de même assez parlant, et je te laisse le constater par toi même.
http://dl.dropbox.com/u/199248/perf.png
http://dl.dropbox.com/u/199248/nb_premier.zip
Sache finalement que mes propos (je dis "mes" mais je pense parler au nom de tous) visait simplement à t'indiquer quelques magies mathématiques qui furent découvertes bien avant nous, faciles à mettre en place dans ton code et permettant un vrai gain de temps... nous ne voulions en aucun cas détruire ton code, il ne fallait pas se sentir martyrisé.
Voilà, en espérant que tu puisse profiter pleinement des ressources offertes par Codes-Sources pour l'apprentissage et la découverte, je te souhiate de passer une bonne journée.
PwOc
9 août 2010 à 10:16
"Ah si ce code n'était là uniquement que pour répondre à un exercice de méthodologie et d'algorithmie ???"
Je pense que justement, si ce code n'est là que pour répondre à un exercice de méthodologie et d'algorithme, alors autant le faire correctement. J'ai eu à faire ces exercices il n'y a pas deux ans de cela, et on nous faisait utiliser systématiquement la racine du nombre comme limite de l'itération. Il y'a surement une raison.
De plus, tu dis que tu programme dans d'autres langages... Si tu parle ici de l'algorithme, le langage n'a pas d'importance. Quelque soit le langage, si tu fait le test de primalité par une boucle, tu utilisera la racine comme limite. Après, il y'a peut être des méthodes plus efficaces, mais pas avec un algorithme identique, ça rends la comparaison absurde.
Quant à ton test, il n'est pas pertinent. Tes nombres premiers sont 97 et 31. Tu as bien des grands nombres, mais ils sont soit pairs, donc divisible par 2 ( 1 tour de boucle ), ou 3 ( 2 tours de boucle ), ça ne donne pas vraiment un test concluant.
Si tu veux recommencer le test, en utilisant, au hasard, le nombre 15648977, par exemple. J'obtiens 13 secondes avec le sqrt, plus de 60 sans (je suis toujours en train d'attendre la fin d'exécution ), pour 10k itérations.
"C'est une perte de temps processeur de vérifier la racine carrée (qui n'est pas forcément un nombre entier avec la fonction PHP)."
"C'est très important de pouvoir gagner des microsecondes de calculs avec un serveur configuré pour tourner dans un mouchoir de poche connecté en 56k et placé à l'autre bout du globe !"
Je te laisse établir toi même la contradiction de tes propos.
Bonne journée.
9 août 2010 à 09:59
Il manque un test :
si $_nombre == 2, c'est un nombre premier.
9 août 2010 à 00:50
9 août 2010 à 00:42
9 août 2010 à 00:21
Pour exemple, j'écris "Pour information : la fonction is_int ne marche que pour les nombres <= 2147483647" pour essayer d'être constructif(comme tu le demandes plus haut) et t'aider à trouver une source d'erreur possible dans ton code mais de ton côté tu le prends comme une critique.
C'est sûr que si tu penses qu'à chaque bout de code que tu vas poster ici tout le monde te diras 'ouah c'est génial! merci on attendait que toi' tu risques de tomber de bien haut. Les gens sont ici non seulement pour partager leur travail (ou une partie) avec les autres mais également pour s'entraider afin que chacun puisse progresser. Apparemment tu n'as pas besoin de l'aide de quiconque, j'en suis content pour toi (c'est sincère) et j'attends le prochain bouquin que tu sortiras qui nous permettra à tous de nous rendre compte à quel point nous sommes incultes (un peu moins sincère).
Sur ces bonnes paroles, bonne semaine tout de même à tout le monde !
9 août 2010 à 00:09
1) La précision se règle au niveau du fichier de configuration
2) Pour plus de performance, j'aurais fait ce code en C avec un bel algorithme très incompréhensible
3) Ah mais si je faisais la division par tout les nombres premier compris entre 1 et l'infini sachant que tout ces nombres serait stocké dans un tableau tout en combinant avec l'exécution d'un script shell côté serveur on ira encore plus vite !
4) Donne moi 1 et 1 seul cas pratique de déterminer les nombres premiers dans du développement web ??? Ah si ce code n'était là uniquement que pour répondre à un exercice de méthodologie et d'algorithmie ??? Mais NON !!! C'est très important de pouvoir gagner des microsecondes de calculs avec un serveur configuré pour tourner dans un mouchoir de poche connecté en 56k et placé à l'autre bout du globe !
5) Je comprends mieux pourquoi certains contributeurs sont partis de ce site ...
8 août 2010 à 23:55
Pour les nombres au-dessus : plantage!!
J'espère que ma remarque est assez constructive pour toi !!
8 août 2010 à 23:49
Mon code fonction avec 15 aussi (voir code source encore une fois)
PS: Dans mon environnement de dev, le Max Time exec est 300 secondes ... et si je vous faire pour des grands nombres, JAMAIS je ne le ferai en PHP ... Il y a d'autres langages de programmation plus adapté !
8 août 2010 à 23:23
8 août 2010 à 23:17
OUI, je sais que le break sert à qui une boucle ! Mais là il ne sert à rien. Test ceci !
<?php
for ($i = 0; $i < 100; $i++)
{
if ($i == 42)
{
return (42);
echo "Hello World";
break;
}
}
?>
Tu verra que le echo n'est pas exécute don le break aussi, car le return est débranchant (équivalant à un exit).
"avec un sqrt() avant de rentrer dans la boucle"
On parle pas en test avant la boucle mais en condition de boucle.
Sinon voici un code qui fonctionne (même avec 124803243)
function is_prime($x)
{
if (!is_int($x)) // C'est un entier ?
return (false);
if (is_int($x / 2)) // Il est divisible par 2 ?
return (false);
$sqrt = sqrt($x);
if (is_int($sqrt)) // Sa racine carrée est entière ?
return (false);
$sqrt = floor($sqrt);
for ($i 3 ; $i < $sqrt; $i $i + 2) // Alors en test de le diviser par tout les nombre impair jusqu'à ca racine.
if (is_int($x / $i))
return (false);
return (true);
}
PS : Ton code plante avec 15. Ton break est mal placé. En le supprimant le code devient juste. MAIS pour le nombre 2038313183 voilà le résultat de ton script : "Fatal error: Maximum execution time of 60 seconds exceeded" le code qui se situe juste au dessus met 0,0192 s a retourner le bon résultat.
PS2 : Pour test avec de gros nombre premier tu peux trouver de gros nombre premier sur http://www.bigprimes.net/
8 août 2010 à 23:08
Pour les autres, j'ai modifié le test comparatif (voir capture et zip pour plus de détails) pour faire 10 000 itérations pour que les différences soient bien mises en évidence.
Si je n'avais pas fait appel à la fonction sqrt() et à l'instruction break, c'est que j'avais mes raisons. La preuve en image et dans le zip !
Cordialement.
8 août 2010 à 22:32
@agparchitecture : Pour 124803243 il y a bien un bug, je vais regarder pourquoi il ne détecte pas que celà n'est pas un nombre premier. Merci pour ta remarque. (enfin une qui est constructive)
8 août 2010 à 22:23
124803243 / 9 13867027 Ce qui en découle qu'il est également divisible par 3> 124803243 / 3 = 41601081
Si ma mémoire est bonne, il me semble que pour savoir si un chiffre est divisible par 3 est de vérifier que la somme des chiffres qui compose le nombre n'est pas divisible par 3.
Il apparait ici que 1+2+4+8+0+3+2+4+3 = 27 (divisible par 3).
Ou bien il y a quelque chose qui m'échappe dans la fonction.
8 août 2010 à 22:03
0.000299 seconde est plus petit que 0.000253 seconde bien entendu !
Tout est dans le zip ...
Le break sert à quitter une boucle de type for(), foreach(), switch() ou while() donc elle sert !!! (Quand on la place au bon endroit je vous l'accorde)
Je ne code pas seulement qu'en PHP mais aussi en Python et en Ruby ... Par conséquent c'est cette syntaxe que je privilégies ! Après si on sait pas lire ...
8 août 2010 à 15:31
J'irai également dans le sens de Biboux et Optitech. Il ne sert à rien de vérifier si le nombre "premier" est bien multiple de nombres supérieurs à la racine de celui-ci (on me suit ? :D). Niveau temps d'exécution, c'est un grand gain de temps en le sens qu'on laisse tomber bien plus de la moitié de éléments à vérifier (ex: si le nombre à vérifier est 97, on n'effectue la boucle que de 2 à 9,84 soit 9 et on sait que 97 est premier).
Autre optimisation possible: Tu continues de vérifier pour tous les nombres pairs... alors que tu sais déjà que le nombre n'était pas multiple de 2... La il s'agit de laisser tomber la moitié des vérifications.
Sinon le code est propre et bien commenté (même si côté syntaxique, la version {} proposée par php est plus lisible)
Bonne continuation
PwOc
8 août 2010 à 14:12
À la ligne juste avant ton break tu à un return. Or return est débranchant, cela signifie que ca quitte la fonction donc ton break n'est jamais éxécuté.
Je confirme ce que dit Biboux, ca ne sert à rien de test ton nombre avec des nombres qui sont au dessus de la racine. Tu divisera ton temps de réponse positive par 2.
Sinon
for (...):
// Code was deleted here
endfor;
ou
if (...):
// code was deleted here
endif;
C'est très moche et ilisible.
8 août 2010 à 13:25
8 août 2010 à 13:12
Mais la fonction sqrt() retourne un float et non un entier. Donc dans la plupart des cas, on sort du cadre des nombres entiers.
Concernant l'optimisation. On peut le faire que dans 1 seul sens, dans mon cas, on détermine plus rapidement si un nombre n'est pas premier. Donc dans le cas contraire, malheureusement, on parcoure la toute boucle.
8 août 2010 à 13:01
Pour la suite, je n'ai pas parlé de pré-vérification! Je t'ai proposé une solution pouvant t'éviter la moitié des passages dans la boucle pour les nombres n'étant pas premiers.
Apparemment tu lis pas ce que j'écris, tant pis pour toi, je cherchais seulement a t'aider!
8 août 2010 à 12:54
Car en général, les entiers sont multiples de 2, 3 et 5 et comme ce sont les premiers à être vérifié dans la boucle. On sort très vite de cette dernière.
Donc non ! C'est une perte de temps processeur de vérifier la racine carrée (qui n'est pas forcément un nombre entier avec la fonction PHP).
8 août 2010 à 12:45
+1 pour la pré-vérification. Çà éviterai de rentrer dans la boucle, si il existe une racine mais si ce n'est pas le cas, la pré-vérification prends du temps processeur pour rien sur des nombres très grand.
8 août 2010 à 12:40
-quand j'ai regardé tout à l'heure, le titre était bien: "....nombre entier", d'où mon 1er commentaire
-pour le 2ème, rien à voir avec ton "break". Si le nombre n'est pas premier, ça t'evitera de parcourir les valeurs supérieures a la racine(car inutile). Cela améliorera vraiment les performances. Ne crois pas m'expliquer ce qu'est un nombre premier, je connais très bien!
Bonne journée a toi !
8 août 2010 à 12:31
8 août 2010 à 12:24
8 août 2010 à 12:23
2) Si je voulais gagner en performance pour déterminer un nombre ENTIER, j'utiliserai la fonction is_int() qui est hard codé et donc ma fonciton serait totalement obsolète puisque je réinvente la roue.
Pour information, un nombre PREMIER est un nombre qui n'est divisible que par 1 et par lui même
8 août 2010 à 12:14
2 petits commentaires sur ta source:
-le titre n'est pas bon je pense('entier' au lieu de 'premier')
-si tu veux gagner énormément en performances, tu peux arrêter ta boucle à racine carrée de nombre(si le nombre est pas multiple d'un nombre en dessous, il sera forcément pas multiple d'un ombre au-dessus). Ainsi ça deviendra:
$racine = sqrt($nombre);
for($i = 2; $i < $racine; $i++)
...etc...
Merci pour ton job!