AFFICHAGE DE LA LISTE DES N PREMIERS NOMBRES PREMIERS.

davwart Messages postés 855 Date d'inscription mardi 19 novembre 2002 Statut Membre Dernière intervention 28 juillet 2009 - 13 févr. 2004 à 16:42
Batshi Messages postés 1 Date d'inscription samedi 30 juin 2012 Statut Membre Dernière intervention 6 juillet 2012 - 6 juil. 2012 à 16:05

Cette discussion concerne un article du site. Pour la consulter dans son contexte d'origine, cliquez sur le lien ci-dessous.

https://codes-sources.commentcamarche.net/source/20382-affichage-de-la-liste-des-n-premiers-nombres-premiers

Batshi Messages postés 1 Date d'inscription samedi 30 juin 2012 Statut Membre Dernière intervention 6 juillet 2012
6 juil. 2012 à 16:05

C bon

cs_prim Messages postés 12 Date d'inscription mardi 17 juin 2003 Statut Membre Dernière intervention 23 mars 2009
14 févr. 2004 à 23:00

franchement bien joué !! j'y avais pensé au crible d'Erastotène mais je ne savais pas comment mettre ca algorithmiquement (ché pas si ca se dit lol); le pire c'est que c franchement rapide comparé a mes boucles sans fin lol
ENCORE BIEN JOUé

cs_prim Messages postés 12 Date d'inscription mardi 17 juin 2003 Statut Membre Dernière intervention 23 mars 2009
14 févr. 2004 à 23:00

cs_Kirua Messages postés 3006 Date d'inscription dimanche 14 avril 2002 Statut Membre Dernière intervention 31 décembre 2008
14 févr. 2004 à 14:00

voilà j'ai corrigé mon code, teste les vitesses des deux pr voir, j'ai pas le temps ici:

<?
$n = 100;

$Naturels = array();
for($i = 0; $i <= $n; $i++) $Naturels[] = 1;

$Naturels[0] = 0;
$Naturels[1] = 0;

for($i = 2; $i <= $n; $i++)
if($Naturels[$i] == 1)
for($j = $i*2; $j <= $n; $j += $i)
$Naturels[$j] = 0;

$Premiers = array();
for($i = 2; $i <= $n; $i++)
if($Naturels[$i]) $Premiers[] = $i;

echo "";
print_r($Premiers);
echo "

";
?>

bonne journée ;-)

cs_Kirua Messages postés 3006 Date d'inscription dimanche 14 avril 2002 Statut Membre Dernière intervention 31 décembre 2008
14 févr. 2004 à 13:48

je te conseil fortement d'utiliser le crible d'eratosthène pour générer une liste de nombres premiers, parce que les opérations modulo (%) sont gourmandes dans une boucle aussi longue. Pour info, j'avais écrit un script de ce genre avec l'opéro modulo pour calculer ts les nb prem < 10 000 000 et ça prenait plusieurs minutes. j'ai repensé mon code en remplaçant les modulo par des "plus" (+), et ça a mis 2,5 secondes (en C++, notez que sur cppfrance un gars a posté un prog qui génère les nb prem < 1 000 000 en 0,067s!)

pour le crible, le principe est simple:

$Naturels = array(); //tableau des naturels jusque $n (0 compris mais on s'en fiche)
for($i = 0; $i <= $n; $i++) $Naturels[] = true;
//la ligne ci-dessus met ts les naturels à true par défaut, donc par défaut ils sont premiers

$Naturels[1] = false; //pas 1, et l'indice 0 est pas utilisé

//mtnt commence l' "astuce", càd qu'on passe ts les Naturels en revue, et chaque fois qu'on rencontre un nombre qui est mis à true (donc qui est premier), on met ts ses multiples à false

for($i = 2; $i <= $n; $i++)
{
if($Naturels[$i] == false) continue; //on passe s'il est composé (= pas premier)

//si on arrive ici, c'est que c'est un nombre premier, donc on passe tous le tableau à la recherche des multiples, c'est ici que j'avais mis mes modulo, mais pr atteindre les multiples ils suffit d'avancer de $i en $i !

for($j = $i; $j <= $n; $j += $i)
$Naturels[$j] = false;
}

//on a donc mtnt un tableau assez grand qui contient true ou false pr ts les naturels jusque n, donc on crée un nouveau tableau dans lequel on ne met que les nombres premiers (les 'true')

$Premiers = array();
for($i = 2; $i <= $n; $i++)
if($Naturels[$i]) $Premiers[] = $i;

et là il s'agit de traiter ce tableau (afficher, sauver ...) et aussi si le script est encore long d'effacer le tableau Naturels, désormais inutile (il faut utiliser unset ou un truc du genre, je sais plus, unlink peut etre)

j'ai tappé ça en live donc je promets pas que le code fonctionne, mais tu as l'idée ;-)

amicalement,

Kirua

cs_prim Messages postés 12 Date d'inscription mardi 17 juin 2003 Statut Membre Dernière intervention 23 mars 2009
13 févr. 2004 à 16:58

oué je penses qu'il y a moyen d'optimiser ça, je v y réfléchir ;)

davwart Messages postés 855 Date d'inscription mardi 19 novembre 2002 Statut Membre Dernière intervention 28 juillet 2009 1
13 févr. 2004 à 16:42

hou là..c bon en theorie.. mais la..effectivment ça va tourner longtmeps..
y'a moyen d'optimier ça..
par exmple ta deuxieme boulce peut s'arreter à i%2 :-)

Discussions similaires

Somme des n premiers entiers.

decomposition d'un nombre en java

Premier jour de la semaine

Calcul du n-ième nombre premier

Listing des marques et modéle de voiture

Votre réponse

Discussions similaires