FONCTION QUI VÉRIFIE SI L'ARGUMENT EST UN NOMBRE PREMIER

Commentaire de biboux le 08/08/2010 12:14:27

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:

$racine = sqrt($nombre);
for($i = 2; $i < $racine; $i++)
...etc...

Merci pour ton job!

Commentaire de darkelda le 08/08/2010 12:24:54

Pour plus d'informations sur les nombres premiers : http://fr.wikipedia.org/wiki/Nombre_premier

Commentaire de biboux le 08/08/2010 12:40:10

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 !

Commentaire de darkelda le 08/08/2010 12:54:11

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).

Commentaire de darkelda le 08/08/2010 13:12:26

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.

Commentaire de Optitech le 08/08/2010 14:12:28

"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.

Commentaire de darkelda le 08/08/2010 22:03: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 ...

Commentaire de darkelda le 08/08/2010 22:32:29

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)

Commentaire de Optitech le 08/08/2010 23:17:28

"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 !

<?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/

Commentaire de darkelda le 08/08/2010 23:49:41

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é !

Commentaire de darkelda le 09/08/2010 00:09:34

"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 ...

Commentaire de Optitech le 09/08/2010 00:42:45

+1 biboux

Commentaire de jeca le 09/08/2010 09:59:23

Bonjour,

Il manque un test :
si $_nombre == 2, c'est un nombre premier.

Commentaire de pwoc le 09/08/2010 11:43:52

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.

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

Commentaire de darkelda le 09/08/2010 12:28:09

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 !

Commentaire de LoveAngel1337 le 09/08/2010 13:01:07

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...

Commentaire de pwoc le 09/08/2010 13:08:19

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))

Commentaire de lynxtyle le 09/08/2010 13:28:53

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...)

Commentaire de lynxtyle le 09/08/2010 14:55:11

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...

Commentaire de lynxtyle le 09/08/2010 16:21:32

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é...

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'; ?><br />
     <?php echo nombre_premier(7)? 'PREMIER' : 'PAS PREMIER';; ?><br />
     <?php echo nombre_premier(11)? 'PREMIER' : 'PAS PREMIER';; ?><br />
     <?php echo nombre_premier(23)? 'PREMIER' : 'PAS PREMIER';; ?><br />
     <?php echo nombre_premier(24)? 'PREMIER' : 'PAS PREMIER';; ?><br />
     <?php echo nombre_premier(31)? 'PREMIER' : 'PAS PREMIER';; ?><br />
     <?php echo nombre_premier(179430059)? 'PREMIER' : 'PAS PREMIER';; ?><br />
     <?php echo nombre_premier(32416190071)? 'PREMIER' : 'PAS PREMIER';; ?><br />
     <?php echo nombre_premier(2038313183)? 'PREMIER' : 'PAS PREMIER';; ?><br />
     <?php echo nombre_premier(-31)? 'PREMIER' : 'PAS PREMIER';; ?><br />
     <?php echo nombre_premier(4.89)? 'PREMIER' : 'PAS PREMIER';; ?><br />
     <?php echo nombre_premier(974365496326392643269543)? 'PREMIER' : 'PAS PREMIER';; ?><br />


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 ;-)

Commentaire de lynxtyle le 10/08/2010 15:16:39

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 :-)