[PYTHON] [Für Wettbewerbsprofis] Zusammenfassung der Primfaktoren, Reduzierungen und Primfaktoren
Primzahlurteil
- Sie müssen nur zu √N aufschauen, um zu beurteilen, ob es teilbar ist.
- Wenn "N = a * b (a <= b)", wenn festgestellt werden kann, dass es durch "a" teilbar ist, muss nicht bestimmt werden, ob es durch "b" teilbar ist.
- Mit anderen Worten, es reicht aus zu beurteilen, ob es maximal auf den Fall von "a = b" aufgeteilt werden kann, so dass es ausreicht, a zu betrachten, das "N = a * b = a * a = a ** 2" erfüllt. ..
- O(√N)
#Primzahlurteil
def isPrime(n: int):
# validation chech
if n < 0:
raise("[ERROR] parameter must be not less than 0 (n >= 0)")
if n == 0 or n == 1:
return False
for i in range(2, n + 1):
#Schauen Sie unten √N. ich*Ich vergleiche es wie ich, weil ich nicht mit Brüchen umgehen will.
if i * i > n:
return True
if n % i == 0:
return False
#Primzahlurteil
N = 7
print(isPrime(N))
# True
Primzahlzählung / Eratostenes-Sieb
- Bereiten Sie eine Liste mit bis zu N vor. Wenn Sie eine Liste finden, die einer Primzahl entspricht, löschen Sie das Vielfache.
- Wie oben, bis zu √N ist OK
- Das mehrfache Löschen wird von "i ** 2" durchgeführt, da "i * (i -1)" im vorherigen Prozess herausgefiltert wurde.
zB) Wenn "i = 5", "5 * 2", "5 * 3" und "5 * 4" alle als Vielfache von 2, Vielfache von 3 und Vielfache von 2 fallen gelassen werden.
#Eratostenes Sieb
#Aufzählung der Primzahlen(Abschnitt kann angegeben werden)
def getPrimes(last: int, first: int = 1):
# validation check
if not isinstance(last, int) or \
not isinstance(first, int):
raise("[ERROR] parameter must be integer")
if last < 0 or first < 0:
raise("[ERROR] parameter must be not less than 0 (first >= 0 & last >= 0)")
if last < first:
last, first = first, last
isPrime = [True] * (last + 1) #Ob es eine Primzahl ist
#0 und 1 bis Falsch
isPrime[0] = isPrime[1] = False
for i in range(2, int(last ** 0.5 + 1)):
if isPrime[i]:
#Sieben. Setzen Sie alle Vielfachen von i auf False. Zu dieser Zeit i^Sie müssen nicht bis zu 2 sehen, da diese bereits herausgefiltert wurden
for j in range(i ** 2, last + 1, i):
isPrime[j] = False
return [i for i in range(first, last + 1) if isPrime[i]]
#Aufzählung der Primzahlen
N = 10 #Einschließlich der letzten Nummer
print(getPrimes(N))
# [2, 3, 5, 7]
#Aufzählung der Primzahlen
F = 13
L = 23 #Einschließlich der letzten Nummer
print(getPrimes(F, L))
# [13, 17, 19, 23]
#Anzahl der Primzahlen
N = 10 ** 7
print(len(getPrimes(N)))
# 664579
# 2.Über 5s
Zahlen aufzählen
Code zum Aufzählen von Brüchen mit hoher Geschwindigkeit (Python) Es kommt sortiert heraus.
#Zahlen aufzählen
def getDivisors(n: int):
# validation check
if not isinstance(n, int):
raise("[ERROR] parameter must be integer")
if n < 0:
raise("[ERROR] parameter must be not less than 0 (n >= 0)")
lowerDivisors, upperDivisors = [], []
i = 1
while i * i <= n:
if n % i == 0:
lowerDivisors.append(i)
if i != n // i:
upperDivisors.append(n//i)
i += 1
return lowerDivisors + upperDivisors[::-1]
#Zahlen aufzählen
N = 120
print(getDivisors(N))
# [1, 2, 3, 4, 5, 6, 8, 10, 12, 15, 20, 24, 30, 40, 60, 120]
Ermitteln der Anzahl der Reduzierungen für mehrere Ganzzahlen (eine andere Methode)
- Sie können von 1 bis N wiederholen, um den Bruch mit dem obigen Code zu erhalten und aus der Länge der Liste zu berechnen, aber eine andere Methode.
- Schleife auf der Bruchseite und zähle diejenigen mit dieser Fraktion.
- Wenn zu diesem Zeitpunkt der Bruch selbst in der Liste enthalten ist, scheint es, dass eine Liste von Brüchen in einem Schuss für mehrere ganze Zahlen erhalten werden kann.
- O (NlogN). Die Aufzählung ist streng, wenn sie 10 ^ 7 beträgt.
#Holen Sie sich die Nummer von ungefähr
def getNumsOfDivisorsOfEachNumbers(n: int):
# validation check
if not isinstance(n, int):
raise("[ERROR] parameter must be integer")
if n < 0:
raise("[ERROR] parameter must be not less than 0 (n >= 0)")
nums = [0] * (n + 1) # 0-indexed
for i in range(1, n + 1):
for j in range(i, n + 1, i):
nums[j] += 1
nums.pop(0)
return nums
#Holen Sie sich die Nummer von ungefähr
N = 10
print(getNumsOfDivisorsOfEachNumbers(N))
Referenz) ABC172 D Problem von AtCoder
Primfaktorisierung
- Sie können es ruhig teilen, aber es ist eine nützliche Methode, wenn Sie die Primfaktoren für mehrere Zahlen gleichzeitig wie oben finden möchten.
- Beschreiben Sie beim Löschen von Vielfachen auf dem Eratostenes-Sieb, anstatt sie mit Flaggen zu verwalten, durch welche Zahl sie geteilt wurden, damit sie nach de verfolgt werden können.
- Erhalten Sie die Primfaktoren auf ähnliche Weise wie beim Verdoppeln.
zB) Zum Beispiel, wenn 10 in Primfaktoren einbezogen werden.
- Siehe 10 in der Liste.
- Da 10 durch 2 geteilt werden kann, fügen Sie 2 zur Primfaktorliste hinzu.
- Siehe den entsprechenden Teil der Erholung 5 von 10/2 = 5. 4.5 wird als 5 geschrieben, und es kann verstanden werden, dass es sich um eine Primzahl handelt, sodass das Urteil abgeschlossen ist.
import time
#Primfaktorisierung
def primeFactrization(n: int):
# validation check
if not isinstance(n, int):
raise("[ERROR] parameter must be integer")
if n < 0:
raise("[ERROR] parameter must be not less than 0 (n >= 0)")
dividableMinimunPrime = [i for i in range(0, n + 1)] #Die kleinste Primzahl, die die Zahl i teilt
for i in range(2, int(n ** 0.5 + 1)):
if dividableMinimunPrime[i] == i:
for j in range(i ** 2, n + 1, i):
if dividableMinimunPrime[j] == j: #Wenn Sie die Bedingung löschen und das Überschreiben zulassen, werden die erhaltenen Primfaktoren in absteigender Reihenfolge angezeigt.
dividableMinimunPrime[j] = i
#Gehen Sie genauso vor wie beim Verdoppeln
primeFactors = []
rest = n
while dividableMinimunPrime[rest] != rest:
primeFactors.append(dividableMinimunPrime[rest])
rest //= dividableMinimunPrime[rest]
primeFactors.append(rest)
return primeFactors
N = 200000
start = time.time()
print(primeFactrization(N))
elapsedTime = time.time() - start
print("time: {} [sec]".format(elapsedTime))
# [2, 2, 2, 2, 2, 2, 5, 5, 5, 5, 5]
# time: 0.05865812301635742 [sec]
# time: 0.07313990592956543 [sec]
# time: 0.05380010604858399 [sec]
Referenz) AtCoder ABC152 E Problem
Recommended Posts