crible d'eratostene en php

[ramy]

Pour ce qui connaissent cet algorithme mathematique enseigné en Terminale, je suis en train d'essayer de le reproduire en php a titre demonstratif...

Voici l'etat actuel du code :

<?php
$premier = file("premier.txt");


///----------------------
///procedure verif premier
///----------------------
$maxi = count($premier)-1;
$max = $premier[$maxi]*$premier[$maxi];


function pgcd($a , $b){ 
if (($a <= 0) || ($b <= 0)) 
 return ("Veuillez passer 2 nombres strictement positifs"); 
 while ($b > 0) 
 { 
 $r = $a % $b; 
 $a = $b; 
 $b = $r; 
 } 
 return $a; 
}


function verif($i) {
for ($j=0; $j<=$maxi; $j++) {
$nb = $premier[$j];
 if ((pgcd($i , $nb)) != 1) {
  $compteur .= $i."\n";
 }
}
}



for ($i=$premier[$maxi+1]; $i<=$max; $i++) {
verif($i);
}


///----------------------
///ecriture...
///----------------------
$pointeur=fopen("premier.txt","w");
fputs($pointeur,$compteur);
fclose($pointeur);
?>

Le but est d'inscrire dans le fichier 'premier.txt', les nombres $i repondant aux condictions de la fonction verif(). Vous pouvez retrouver ces pages ici : erato.php initialise le crible, permier.php est la page en question alors que permier.txt contient la liste de nombres premiers... Malheuresement, ce code ne fonctionne pas bien qu'il ne produise pas d'erreur

PS : si certain de connaisse pas le crible d'eratostene je me ferais un plaisir de l'expliqur ici... surtout si ça peut faire avancer ce code

[kmlz]

Houlala, le crible d'Ératosthène permet justement de trouver les nombres premiers sans avoir à utiliser la méthode d'Euclide (ta fonction pgcd). Il est décrit ici.

J'ai fait un algorithme en PHP. Je l'ai traduit d'un algo en C que j'ai fait il y a quelques temps déjà donc ce n'est surement pas très optimisé . J'ai essayé d'expliquer le plus clairement possible. Si jamais tu as des questions n'hésite pas.

<?php

/* Le but est de déterminer la liste des nombres premiers inférieurs à $taille 
Pour ce faire, ma méthode est de faire un tableau de $taille cases. Lorsque $tab[$i]=1 cela signifie que le nombre est premier.
Si $tab[$i]=0 le nombre $i n'est pas premier. */

function eratosthene($taille)
{
/* On initialise notre tableau a une valeur bidon (ici 9) */
for($x=0;$x<$taille;$x++) $tab[$x]=9;
/* Cas du 0 et du 1 */
$tab[0]=$tab[1]=0;
/* Initialisation des variables */
$i=2; $n=2;
/* Debut du crible d'Eratothène */
while( ($i*$i) < $taille) 
{
$j=$i;
/* Si le nombre n'a pas été traité précédemment et qu'il est multiple de $n il est premier*/
if(!($n%$i) && $tab[$i]==9)
{
 $tab[$i]=1;
 /* On raye tous les multiples de $i */
 $i+=$j;
 while($i<$taille) { $tab[$i]=0; $i+=$j; }
}
/* Sinon il n'est pas premier */
else $tab[$i]=0;
/* Incrémentation des variables */
$i=$j;
$i++;
$n++;
}
/* Les nombres "oubliés" sont premiers. On reparcourt le tableau */
for($x=0;$x<$taille;$x++) if($tab[$x]==9) $tab[$x]=1;
return $tab;
}

$size=20;
$blah=eratosthene($size);
$hu=fopen("premier.txt","w");
for($x=0;$x<$size;$x++) if($blah[$x]==1) fwrite($hu,$x."\n");
fclose($hu);

?> 

[XyLiS]

Quel bogoss ce Kmlz, vive kmlz

[ingeni]

Voilà ma solution:

<?php
$fichier = fopen('./result.txt', "w");

$max = 100;

//tableau des premiers
$tab_premier[0] = 1;
$tab_premier[1] = 2;

//indice de parcours du tableau
$indice_tab = 2;

//init du nombre
$i = 3;

//$i varie de 3 à $max
while($i <= $max)
{
//tag de détection
$tag = 0;
//on parcourt le tableau des premiers
foreach ($tab_premier as $indice=>$valeur)
{
 //on exclue la valeur 1 (bidouille)
 if ($valeur != 1 && $i % $valeur == 0)
 {
 	//nombre non premier
 	$tag = 1;
 	break;
 }

}

//cas d'un nombre premier
if (!$tag)
{
 $tab_premier[$indice_tab++] = $i;
 fwrite($fichier,$i."\n");

}

$i++;
}

//fermeture fichier
fclose($fichier);

//petit affichage gentil
echo "Sortie résultat:<br>";
foreach($tab_premier as $indice=>$valeur)
{
echo "$indice=>$valeur<br>";
}
?>