Als ich beim Atcoder Biginner Contest170 sah, dass die Idee des Eratostinesiebens angewendet wurde, beschloss ich, sie zu schreiben, da ich dachte, ich sollte das Eratostinensieben nicht einmal richtig verstehen. Dieser Artikel dient eher dem Verständnis des Prinzips als der praktischen Anwendbarkeit. Wenn Sie also während des Wettbewerbs usw. angekommen sind hier Ist empfohlen. (Dies ist die Website von Herrn Takotsubo, der immer eine Referenz ist)
Zunächst verwenden wir eine Methode, die als Trial-Split-Methode bezeichnet wird. Es ist keine Primzahl, weil es in der Reihenfolge durch eine Zahl größer als 2 geteilt wird, und wenn es teilbar ist, hat es diese Zahl als Bruch. Es ist jedoch nicht erforderlich, durch alle Zahlen bis zu $ N $ zu teilen. Wenn $ N $ einen Bruchteil von $ d $ hat, dann ist $ N / d $ auch ein Bruchteil von $ N $, je nachdem, welcher Wert kleiner ist, ist ausreichend. Der kleinere ist der größte, wenn diese beiden gleich sind. Es reicht also aus, bis zu $ \ sqrt {N} $ zu schauen (der kleinere wird entfernt und der größere ist bereits aktiviert). Aus dem Obigen kann diese Primzahlbeurteilung mit $ O (\ sqrt {N}) $ berechnet werden. Wenn Sie eine gerade Zahl als Bruch haben, sollte diese aus Gründen der Beschleunigung durch 2 teilbar sein. Nach 2 sollten Sie also nur die ungerade Zahl überprüfen. (Diesmal nicht berücksichtigt)
# 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
Als nächstes schauen wir uns eine Technik an, die Eratostinesieben heißt. Dies ist die Idee, dass alle Primzahlen unter $ N $ aufgelistet werden. Wenn mehrere Ziele zu beurteilen sind, kann nach der Vorverarbeitung mit $ O (1) $ beurteilt werden. Der Nachteil ist, dass ein Array der Größe $ N $ erforderlich ist, was die Speichernutzung erhöht.
Nun wollen wir sehen, wie man eine Primzahlentabelle erstellt. Betrachten Sie zunächst alle Zahlen als Kandidaten für Primzahlen. Da 1 keine Primzahl ist, werde ich sie aus den Kandidaten löschen. (Zur Vereinfachung des Arrays ist auch 0 enthalten, aber es ist keine Primzahl, daher wird es implementiert, um es zu löschen.)
Schauen Sie sich als nächstes die Zahlen von der kleinsten in der Reihenfolge von 2 an. Wenn die Zahl eine Primzahl ist, ist das Vielfache die zusammengesetzte Zahl. Daher werden alle Vielfachen aus den Kandidaten gelöscht. Es scheint ein Eratostenes-Sieb genannt zu werden, weil es auf diese Weise gefiltert und von den Kandidaten entfernt zu werden scheint.
Der Umfang der Berechnung ist etwas kompliziert, aber ich werde Ihnen einige Kenntnisse geben. Die Häufigkeit, mit der durch jede Primzahl geteilt werden kann, beträgt $ N / p $ mal, wenn die Primzahl p ist und Sie nur die erste schreiben
# 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
Da es sich um eine zurückzugebende Primzahlentabelle handelt, werde ich vorerst schreiben, wie man sie verwendet.
n = 10
is_prime = eratosthenes_sieve(n)
print(is_prime[5]) # True
print(is_prime[10]) # False
・ HP von Takotsubo-san ・ [Programmierwettbewerbs-Herausforderungsbuch](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