Accueil > > > CRIBLE D'ÉRATOSTHÈNE - LES NOMBRES PREMIERS
CRIBLE D'ÉRATOSTHÈNE - LES NOMBRES PREMIERS
Information sur la source
Description
Voilà une source fait en vitesse pour trouver si un nombre est premier d'une facon très rapide grace au crible d'Ératosthène. La raison de cette source ? http://www.phpcs.com/codes/SPIRALE-ULAM-NOMBRES-P REMIERS_42487.aspx Possaidait une facon de calculer un nombre premier juste, mais un peut lent a mon gout. Source du crible : http://fr.wikipedia.org/wiki/%C3%89ratosth%C3%A8 ne
Source
- <?php
- // Crible d'Ératosthène
-
- //Tableau du crible
- $Nombres_Premiers = array();
-
- function Cree_Crible($Max)
- {
- global $Nombres_Premiers;
-
- if($Max < 2) return 0;
-
- //Par défaut, tous les nombres sont premiers
- for($n = 2 ; $n <= $Max ; $n++)
- $Nombres_Premiers[$n] = TRUE;
- // Sauf pour 0 et 1
- $Nombres_Premiers[0] = $Nombres_Premiers[1] = FALSE;
- // On raye les nombres non premiers
- for($n = 2 ; $n <= $Max ; $n++)
- {
- if($Nombres_Premiers[$n] === TRUE)//Si le nombre est premier
- for($Multiple = 2 ; ($Multiple * $n) <= $Max ; $Multiple ++)//Pour tous ses multiples
- $Nombres_Premiers[$Multiple * $n] = FALSE;//On les concidèrent non premiers
- }
- return 1;
- }
-
- function est_premier($Nombre)
- {
- global $Nombres_Premiers;
- return (bool)$Nombres_Premiers[$Nombre];
- }
-
-
- Cree_Crible(65000);
- echo 'Nombres premier entre 0 et 65000 :<br/>'."\n";
- for($i = 0 ; $i <= 65000 ; $i++)
- if(est_premier($i))
- echo $i."<br/>\n";
- ?>
<?php
// Crible d'Ératosthène
//Tableau du crible
$Nombres_Premiers = array();
function Cree_Crible($Max)
{
global $Nombres_Premiers;
if($Max < 2) return 0;
//Par défaut, tous les nombres sont premiers
for($n = 2 ; $n <= $Max ; $n++)
$Nombres_Premiers[$n] = TRUE;
// Sauf pour 0 et 1
$Nombres_Premiers[0] = $Nombres_Premiers[1] = FALSE;
// On raye les nombres non premiers
for($n = 2 ; $n <= $Max ; $n++)
{
if($Nombres_Premiers[$n] === TRUE)//Si le nombre est premier
for($Multiple = 2 ; ($Multiple * $n) <= $Max ; $Multiple ++)//Pour tous ses multiples
$Nombres_Premiers[$Multiple * $n] = FALSE;//On les concidèrent non premiers
}
return 1;
}
function est_premier($Nombre)
{
global $Nombres_Premiers;
return (bool)$Nombres_Premiers[$Nombre];
}
Cree_Crible(65000);
echo 'Nombres premier entre 0 et 65000 :<br/>'."\n";
for($i = 0 ; $i <= 65000 ; $i++)
if(est_premier($i))
echo $i."<br/>\n";
?>
Conclusion
Défaut : Pour trouver si un grand nombre est premier, il faudra passer dabord par tous les autres.
Avantages : Très rapide lorsqu'on veut tester plusieurs nombre en quelques "nanosecondes" Un crible peut être enregistrer et réutiliser. ex : Si vous utilisez ceci dans un site, vous pouvez générer un fichier allant de 0 à 100 000, puis le réutiliser pour toutes les demandes de nombres premier.
Code débutant, rien d'extraordinaire, juste de la logique ...
Sources de la même categorie
Commentaires et avis
Discussions en rapport avec ce code source dans le forum
MySQL - Ordonner des nombres [ par psychodingue ]
Alors voilà mon prob:Je voudrai ordonner par ordre inverse des nombres, alors j'me connecte à ma base de donner puis je fait:ORDER BY clics DESCJe fou
Splitter un texte en nombres [ par JMGR ]
Je cherche à stocker les forum déja vus par les utilisateurs d'un forum que je crée, mais je ne désire pas utiliser le cookies qui sont je trouve, com
Nombres entier [ par ekinoks ]
he... escusé moi mais he .... comment on fait pour avoir que les nombres entier de nombres decimoexemple :<?$truk = 3/2;echo $truk; //g envi qeu ic
plus rapide que msql_result [ par Isengard ]
Bonjour a tous.Je me rappelle avoir vu qqpart (oui oui) qu'il existait un moyen plus rapide que mysql_result.Par exemple j'ai une toable ou chaque lig
Grille de nombres [ par Tomcube ]
Salu,J'shui en train de faire un script de loto.A peine commencé, déjà un truc qui m'énerve : la grille de nombres. Je veux faire la même grille que s
Nombres de jours entre 2 dates! [ par jimmy69 ]
Bonjour a tous,Voila j'ai un p'tit stress ....si quelqu'un pouvait m'aider!En fait j'enregistre mes donnees ds une table mysql , des donnees comme le
récupérer les 7 premiers chiffre de l'IP [ par pyranhaz ]
Bonjour,J'aimerais pouvoir récupérer seulement les 7 premiers chiffres de $REMOTE_ADDR;C'est possible ???mon script anti-aspirateur serait davantage e
Suite de nombres [ par jak123 ]
Bonjour, j'ai codé une page photos, mon seul hic c'est que j'aimerai que mon chiffre 1 sur mon code ci-dessus, prenne les valeurs de 1 au nombre que j
Chaine de caractère [ par dao85 ]
BonjourJe débute juste en PHP et, après avoir écrit mes premiers scripts, je me heurte à un problème.Je souhaite simplement extraire les 5 premiers ca
définir un répertoire par défaut pour un upload rapide [ par skmancuso ]
Bonjour,Je souhaiterais savoir s'il y a un moyen quelconque de définir un répertoire par défaut avec la balise input type=file.Je suis
|
Derniers Blogs
GESTION D'EXCEPTION AVEC LES TASKSGESTION D'EXCEPTION AVEC LES TASKS par richardc
Nous avons vu dans un précédent article comment utiliser Task pour effectuer des opérations dans un autre thread.
Malheureusement, comme tout le monde n'est pas parfait, il se peut que cette exécution se passe mal et qu'une exception se produise.
La...
Cliquez pour lire la suite de l'article par richardc DéMARRONS AVEC LES TASKSDéMARRONS AVEC LES TASKS par richardc
Que vous le vouliez ou non, le développement multi-tâche est maintenant une obligation pour toute nouvelle application. Il est donc vital d'en comprendre les mécanismes et de s'y mettre le plus tôt possible.
En attendant le .NET Framework 4.5 avec le...
Cliquez pour lire la suite de l'article par richardc SLIDE & DéMO TECHDAYS 2012 - FAST & FURIOUS XAML APPSSLIDE & DéMO TECHDAYS 2012 - FAST & FURIOUS XAML APPS par Vko
Retrouvez les slides et les démo de ma session Fast & Furious XAML Apps. A ceux qui se posent la question : "est-ce que le code de la DataGrid est disponible?", je vous répondrais "pas encore". Je vais mettre en place un projet codeplex pour part...
Cliquez pour lire la suite de l'article par Vko XNA IS DEAD!XNA IS DEAD! par richardc
Depuis la semaine dernière (et grâce aux TechDays 2012), je me penche activement sur la nouvelle version de Windows, aka Windows 8. Vous me direz, il était temps puisque la première preview date de Septembre dernier.
OK. Remarquez, on n'en est qu'aux...
Cliquez pour lire la suite de l'article par richardc TECHDAYS PARIS 2012 : WINDOWS SERVER "8" QUOI DE 9 !TECHDAYS PARIS 2012 : WINDOWS SERVER "8" QUOI DE 9 ! par ROMELARD Fabrice
Speakers: Fabrice Meillon et Stanislas Quastana Cette session est basée entièrement sur celle donnée lors de la BUILD cet hiver. Il n'y a pas d'ajout d'information en rapport avec cet évènement passé. Windows 8 Server sera intégralem...
Cliquez pour lire la suite de l'article par ROMELARD Fabrice
Logiciels
DocTranslate (V3.1.0.0)DOCTRANSLATE (V3.1.0.0)DocTranslate est un traducteur de document Microsoft Word, PowerPoint et Excel. Il permet d'autom... Cliquez pour télécharger DocTranslate Tribler (2012)TRIBLER (2012)Tribler est un client pair à pair (P2P/Peer-to-Peer) open source avec la capacité de regarder des... Cliquez pour télécharger Tribler OneSwarm (2012)ONESWARM (2012)Le peer-to-peer qui protège votre vie privée, c'est OneSwarm.
Ce logiciel de peer-to-peer crypté... Cliquez pour télécharger OneSwarm PONAMEDIA PREMIUM - HELLLOOO FLASH DEMO (V8.4)PONAMEDIA PREMIUM - HELLLOOO FLASH DEMO (V8.4)PONAMEDIA TV DEVIENS HELLLOOO FLASH
LA TV SUR VOTRE ORDINATEUR.
Toute une plateforme Multi... Cliquez pour télécharger PONAMEDIA PREMIUM - HELLLOOO FLASH DEMO Academy System (17.2.1.0)ACADEMY SYSTEM (17.2.1.0)Logiciel de gestion des établissements.
- élèves/étudiants (inscription, dossier, absence...)
-... Cliquez pour télécharger Academy System
|