PHPfrance

la communauté d'entraide francophone dédiée au PHP

Nombres premiers

Répondre


Cette question est un moyen d’empêcher des soumissions automatisées de formulaires par des robots.
Smileys
:D :) :( :o :shock: :? 8-) :lol: :x :P :oops: :cry: :evil: :twisted: :roll: :wink: :!: :?: :idea: :arrow: :| :mrgreen: =D> #-o =P~ :^o :non: :priere: 8-|
Voir plus de smileys
  Revue du sujet
 

  Étendre la vue Revue du sujet : Nombres premiers

Re: Nombres premiers

par Spols » 22 déc. 2010, 14:06

tu as raison sur le problème de racine

l'increment de 2 est proposé dans mon code, et ne tester que les nombres premiers revient à beaucoup moins de test pour des grands nombres, le problème se situe plutot dans la mémoire nécessaire au stockage des nombres premiers.

La vrai question à se poser en premier, jusqu'au envisage t on d'aller ?

Re: Nombres premiers

par Mazarini » 22 déc. 2010, 12:44

Bonjour,
...
-un nombre ne peut pas être divisible par un nombre supérieur à sa racine
...
C'est plutôt que si un nombre est divisible par un nombre plus grand que sa racine, on trouvera le nombre plus petit qui lui correspond avant.
18 est divisible par 9, mais on tombe sur 2 avant.

Pour ce qui est de l'idée de ne tester qu'avec des nombres premiers, on peut simplement faire un incrément de 2 au lieu de 1 ($i++ remplacer par $i+=2) pour réduire le temps de traitement. Ce à condition de traiter $i = 2 et de commencer la boucle à $i = 3.

Re: Nombres premiers

par Spols » 21 déc. 2010, 17:42

La solution est fonctionnelle, mais pas optimisé. Pour des recherches sur un grands nombre de nombre cela se ressentira.

Il est possible de l'optimiser en utilisant les constatation du premier code.
-si un nombre n'est pas paire, (pas divisible par 2 qui est le premier test) il ne sera pas divisible par un nombre paire.
-un nombre ne peut pas être divisible par un nombre supérieur à sa raçine
<?php

$nb = 1;
$nb_max = 50;

while ($nb <= $nb_max) {
        if ($nb == 1) {
        echo $nb.' n\'est pas un nombre premier<br>';
        $nb++;
        continue;
        }
$a = 0;
if (!is_int($nb/2)){
$racine = ;//Je sais plus de tête le code de calcul d'une racine
        for ($i=3; $i<$racine; $i = $i+2){
        
                if (is_int($nb/$i)){
                $a++;
                echo $nb.' n\'est pas un nombre premier<br>';
                break;
                }
        }
}
else
{
echo $nb.' n\'est pas un nombre premier<br>';
$nb++;
continue;
}
if ($a == 0) echo '<b>'.$nb.' est un nombre premier</b><br>';
$nb++;
}

?>

Mieux encore, stocké les nombres premiers dans une array et ne tester que la divisibilité sur ceux ci (tester la divisibilité par 9 est inutile si on l'a déja testé pour 3)
Mais je laisse ceci en exercice

Re: Nombres premiers

par ndmsp » 21 déc. 2010, 10:22

Bonjour,
Merci beaucoup de vos précisions, c'est parfait. Je ne connaissais pas toutes ces syntaxes, ce qui explique pourquoi je galérais un peu !!
Merci encore, j'ai tout compris !!
A++

Re: Nombres premiers

par devlop78 » 21 déc. 2010, 03:46

On essaye de diviser $nb par $i qui prend la valeur de tous les nombres de 2 à $nb
Si $nb/$i est un entier on interrompt le traitement de la boucle car $nb est divisible par $i

En sortie de boucle for, si $a vaut 0, c'est que la boucle n'a pas été interrompu par le if et n'est pas passé par le $a++. Donc le nombre est premier.
Exactement, à une précision près $i prend la valeur de tous les nombres de 2 à $nb-1 car un nombre est tjs divisible par lui même et par 1 :)
C'est la définition même du nombre premier :p

Re: Nombres premiers

par teebo » 20 déc. 2010, 20:31

On essaye de diviser $nb par $i qui prend la valeur de tous les nombres de 2 à $nb
Si $nb/$i est un entier on interrompt le traitement de la boucle car $nb est divisible par $i

En sortie de boucle for, si $a vaut 0, c'est que la boucle n'a pas été interrompu par le if et n'est pas passé par le $a++. Donc le nombre est premier.
Exactement, à une précision près $i prend la valeur de tous les nombres de 2 à $nb-1 car un nombre est tjs divisible par lui même et par 1 :)

Re: Nombres premiers

par Mazarini » 20 déc. 2010, 17:15

On essaye de diviser $nb par $i qui prend la valeur de tous les nombres de 2 à $nb
Si $nb/$i est un entier on interrompt le traitement de la boucle car $nb est divisible par $i

En sortie de boucle for, si $a vaut 0, c'est que la boucle n'a pas été interrompu par le if et n'est pas passé par le $a++. Donc le nombre est premier.

Re: Nombres premiers

par ndmsp » 20 déc. 2010, 13:19

Bonsoir,
Oui, résolu car le code marche, mais je suis là pour apprendre...
Je ne comprends pas cette partie là: 
$a = 0;
		for($i=2; $i<$nb; $i++){
			if (is_int($nb/$i)){
				$a++;
				echo $nb.' n\'est pas un nombre premier<br>';
				break;
			}
		}
Elle teste tous les diviseurs du nombre, n'est-ce pas ? Pourriez vous la détailler ? Merci !

Re: Nombres premiers

par devlop78 » 19 déc. 2010, 21:06

lol je crois que le sujet est résolu :p

Re: Nombres premiers

par teebo » 19 déc. 2010, 20:31

Salut,

J'ai pas chercher l'erreur mais ton script me parait un peu lourd voici comment j'aurais fait : 
<?php

$nb = 1;
$nb_max = 50;

while ($nb <= $nb_max) {
	if ($nb == 1) {
	echo $nb.' n\'est pas un nombre premier<br>';
	$nb++;
	continue;
	}
$a = 0;
	for ($i=2; $i<$nb; $i++){
	
		if (is_int($nb/$i)){
		$a++;
		echo $nb.' n\'est pas un nombre premier<br>';
		break;
		}
	}
if ($a == 0) echo '<b>'.$nb.' est un nombre premier</b><br>';
$nb++;
}

?>

Nombres premiers

par ndmsp » 19 déc. 2010, 11:51

Bonjour,
Je commence en Php, et j'ai fait un petit script php en partant d'un programme de calcul pour déterminer les nombres premiers de 1 jusqu'à une valeur donnée.
Cela marche jusqu'à 7, mais après, il calcule en boucle pour 9 sans s'arrêter. Le problème est que depuis hier soir, je ne trouve pas mon erreur... #-o
Voici le code: 
<?php

	$nombre = 2;
	$max = 50;
	
	while($nombre <= 50){
	
		if($nombre == 1){
			echo $nombre.' n\'est pas premier<br />';}
		else{
			if($nombre == 2){
				echo $nombre.' est premier<br />';}
			
			else{
			
				$calcul = $nombre % 2;
			
				if($calcul == 0){
					echo $nombre.' n\'est pas premier<br />';}
				
				else{
			
					$racine = sqrt($nombre);
					if(is_int($racine)){
						echo $nombre.' n\'est pas premier<br />';}
					
					else{
	
						for($i = 3; $i <= $racine; $i+2){
							$calcul_a = $nombre % $i;
							if($calcul_a = 0){
								echo $nombre.' est pas premier<br />';}
							else{
								echo $nombre.' est premier<br />';}
						}}
					echo $nombre.' est premier<br />';
					}
			}}
			$nombre+2;
			
	}
	
?>
Sauriez vous où elle est ?
Merci !!