Français
Français
Les nombres premiers se réfèrent à des nombres naturels qui ne peuvent être divisibles que par 1 et lui-même. Trouver des nombres premiers est l'un des problèmes courants de la programmation. Cet article présente une méthode de solution de nombres premiers classique et efficace - tamis des eratosthènes. Cet algorithme trouve rapidement tous les nombres premiers dans une plage spécifiée en marquant les nombres premiers et leurs multiples.
La méthode de filtrage Elatoseni est un algorithme de longue date, simple et efficace, et ses idées de base comprennent:
Créez un tableau booléen de longueur n + 1, avec les valeurs initiales de True;
À partir de 2, Mark Multiples de chaque nombre primaire comme faux;
L'élément avec la valeur finale restante de True est un nombre premier.
L'exemple de code suivant montre comment implémenter cette méthode de filtrage à l'aide de PHP:
function sieveOfEratosthenes($n) {
// Créer une longueur de n+1 Booléen，La valeur initiale est true
$isPrime = array_fill(2, $n - 1, true);
// depuis2commencer，Marquez les multiples de chaque nombre premier comme false
for ($i = 2; $i * $i <= $n; $i++) {
if ($isPrime[$i]) {
for ($j = $i * $i; $j <= $n; $j += $i) {
$isPrime[$j] = false;
}
}
}
// Collectionner tout comme true Nombre de，C'est-à-dire des nombres premiers
$primes = [];
foreach ($isPrime as $number => $is) {
if ($is) {
$primes[] = $number;
}
}
return $primes;
}
$range = 100;
$primes = sieveOfEratosthenes($range);
// Numéro primaire de sortie
foreach ($primes as $prime) {
echo $prime . " ";
}
Le code crée d'abord un tableau booléen de taille n + 1, le définit initialement sur true, puis marque les multiples des nombres premiers un par un via une boucle à double couche comme faux un par un. Enfin, tous les index marqués True sont collectés, c'est-à-dire l'ensemble de nombres premiers.
Exécutez le code ci-dessus et la sortie des nombres premiers avec une plage de 100 est la suivante:
<span class="fun">2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97</span>
On peut voir que cette méthode peut trouver avec précision et efficacement tous les nombres premiers dans une plage donnée.
La complexité temporelle de la méthode de filtrage d'Elatoseni est d'environ O (n log n log n), qui convient au dépistage rapide des nombres premiers dans une petite à moyenne portée. Par rapport au jugement violent, davantage de nombres non prioritaires sont exclus chaque fois que le dépistage est considérablement amélioré.
Cet article présente la méthode de filtrage Elatoseni implémentée par PHP, qui est un algorithme de dépistage de nombres premiers simple et efficace. La maîtrise de cet algorithme peut aider à résoudre des problèmes de programmation impliquant des nombres premiers et améliorer l'efficacité et les performances du code.
