A Atcoder Biginner Contest170, quand j'ai vu que l'idée du tamisage des ératostines était appliquée, j'ai décidé de l'écrire, pensant que je ne devrais même pas comprendre correctement le tamisage des ératostines. Cet article vise à comprendre le principe plutôt que l'aspect pratique, donc si vous êtes arrivé pendant le concours, etc. ici Est recommandé. (Ceci est le site de M. Takotsubo, qui est toujours une référence)
Tout d'abord, nous utilisons une méthode appelée méthode de partage d'essai. Ce n'est pas un nombre premier car il se divise dans l'ordre par un nombre supérieur à 2, et s'il est divisible, il a ce nombre sous forme de fraction. Cependant, il n'est pas nécessaire de diviser par tous les nombres jusqu'à $ N $. Si $ N $ a une fraction de $ d $, alors $ N / d $ est également une fraction de $ N $, la valeur la plus petite étant suffisante. Le plus petit est le plus grand quand ces deux sont égaux, il suffit donc de rechercher $ \ sqrt {N} $ (le plus petit est supprimé et le plus grand est déjà vérifié). D'après ce qui précède, ce jugement de nombre premier peut être calculé avec $ O (\ sqrt {N}) $. Ici, pour accélérer, si vous avez un nombre pair en tant que fraction, il devrait être divisible par 2, il semble donc que vous ne devriez vérifier que le nombre impair après 2. (Non pris en compte cette fois)
# O(√N)
def is_prime(n):
if n == 1:
return True
for i in range(2, int(n**0.5) + 1):
if n % i == 0:
return False
return True
Ensuite, regardons une technique appelée tamisage d'ératostines. C'est l'idée que tous les nombres premiers inférieurs à $ N $ seront listés, et s'il y a plusieurs cibles à juger, il sera possible de juger avec $ O (1) $ après le prétraitement. L'inconvénient est qu'il nécessite un tableau de taille $ N $, ce qui augmente l'utilisation de la mémoire.
Voyons maintenant comment créer une table de nombres premiers. Tout d'abord, considérez tous les nombres comme des candidats aux nombres premiers. Puisque 1 n'est pas un nombre premier, je le supprimerai des candidats. (Pour la commodité du tableau, 0 est également inclus, mais ce n'est pas un nombre premier, il est donc implémenté pour le supprimer)
Ensuite, regardez les nombres du plus petit dans l'ordre de 2, et si le nombre est un nombre premier, le multiple est le nombre composé. Par conséquent, tous les multiples seront supprimés des candidats. Il semble être appelé un tamis Eratostenes car il semble être filtré et supprimé des candidats de cette manière.
La quantité de calcul est un peu compliquée, mais je vais vous donner quelques connaissances. Le nombre de fois qui peut être divisé par chaque nombre premier est $ N / p $ fois si le nombre premier est p, et si vous n'écrivez que le premier
# O(NloglogN)
def eratosthenes_sieve(n):
is_prime = [True]*(n + 1)
is_prime[0] = is_prime[1] = False
for p in range(2, n + 1):
if is_prime[p]:
for q in range(2*p, n + 1, p):
is_prime[q] = False
return is_prime
Puisqu'il s'agit d'une table de nombres premiers à renvoyer, j'écrirai comment l'utiliser pour le moment.
n = 10
is_prime = eratosthenes_sieve(n)
print(is_prime[5]) # True
print(is_prime[10]) # False
・ Les PV de Takotsubo-san ・ [Livre du défi du concours de programmation](https://www.amazon.co.jp/%E3%83%97%E3%83%AD%E3%82%B0%E3%83%A9%E3%83%9F % E3% 83% B3% E3% 82% B0% E3% 82% B3% E3% 83% B3% E3% 83% 86% E3% 82% B9% E3% 83% 88% E3% 83% 81% E3 % 83% A3% E3% 83% AC% E3% 83% B3% E3% 82% B8% E3% 83% 96% E3% 83% 83% E3% 82% AF-% E7% AC% AC2% E7% 89% 88-% EF% BD% 9E% E5% 95% 8F% E9% A1% 8C% E8% A7% A3% E6% B1% BA% E3% 81% AE% E3% 82% A2% E3% 83 % AB% E3% 82% B4% E3% 83% AA% E3% 82% BA% E3% 83% A0% E6% B4% BB% E7% 94% A8% E5% 8A% 9B% E3% 81% A8 % E3% 82% B3% E3% 83% BC% E3% 83% 87% E3% 82% A3% E3% 83% B3% E3% 82% B0% E3% 83% 86% E3% 82% AF% E3 % 83% 8B% E3% 83% 83% E3% 82% AF% E3% 82% 92% E9% 8D% 9B% E3% 81% 88% E3% 82% 8B% EF% BD% 9E-% E7% A7% 8B% E8% 91% 89-% E6% 8B% 93% E5% 93% 89-ebook / dp / B00CY9256C)
Recommended Posts