Ich benutze oft Primzahlen und Brüche in Python, aber ich habe es geschrieben, weil es keine Bibliothek gab, die Primzahlen und Brüche verarbeitet.
Es gibt "Trial Division" und "Eratostines Sieb" als alte Algorithmen für die Beurteilung von Primzahlen und die Aufzählung von Primzahlen.
Implementierung aus der Definition von Primzahlen berücksichtigt. Gibt True zurück, wenn alle 2 oder mehr und weniger als $ \ sqrt {num} $ nicht durch eine Ganzzahl teilbar sind.
import math
def is_prime_1(num):
if num < 2:
return False
else:
num_sqrt = math.floor(math.sqrt(num))
for prime in range(2, num_sqrt + 1):
if num % prime == 0:
return False
break
return True
Implementierung mit Trial Split.
def is_prime_2(num):
if num < 2:
return False
if num == 2 or num == 3 or num == 5:
return True
if num % 2 == 0 or num % 3 == 0 or num % 5 == 0:
return False
#Pseudo-Primzahl(Zahlen, die nicht durch 2, 3 oder 5 teilbar sind)Teilen Sie einen nach dem anderen
prime = 7
step = 4
num_sqrt = math.sqrt(num)
while prime <= num_sqrt:
if num % prime == 0:
return False
prime += step
step = 6 - step
return True
Wenn man die Ausführungsgeschwindigkeit vergleicht, ist der Test-Split sicherlich schneller.
%timeit is_prime_1(random.randrange(10 ** 5))
%timeit is_prime_2(random.randrange(10 ** 5))
100000 loops, best of 3: 3.67 µs per loop
100000 loops, best of 3: 2.84 µs per loop
Implementierung unter Verwendung des oben implementierten Primzahlurteils.
def make_prime_list_1(num):
if num < 2:
return []
prime_list = []
for prime in range(2, num + 1):
if is_prime_2(prime):
prime_list.append(prime)
return prime_list
Montage mit einem Eratostenes-Sieb.
def make_prime_list_2(num):
if num < 2:
return []
#0 ist keine Primzahl
prime_list = [i for i in range(num + 1)]
prime_list[1] = 0 #1 ist keine Primzahl
num_sqrt = math.sqrt(num)
for prime in prime_list:
if prime == 0:
continue
if prime > num_sqrt:
break
for non_prime in range(2 * prime, num, prime):
prime_list[non_prime] = 0
return [prime for prime in prime_list if prime != 0]
Vergleichen Sie die Ausführungsgeschwindigkeiten. Eratostenes Sieben ist schneller.
%timeit -n1000 make_prime_list_1(random.randrange(10 ** 5))
%timeit -n1000 make_prime_list_2(random.randrange(10 ** 5))
1000 loops, best of 3: 69.5 ms per loop
1000 loops, best of 3: 10.5 ms per loop
Übrigens ist es extrem langsam, zuerst eine Primzahlentabelle zu erstellen und eine Primzahlbeurteilung durchzuführen.
prime_list = make_prime_list_2(10 ** 5)
def is_prime_3(num):
return num in prime_list
%timeit is_prime_3(random.randrange(10 ** 5))
10000 loops, best of 3: 189 µs per loop
Sie können die Anzahl der Brüche mithilfe der Primfaktorisierung ermitteln.
Implementierung mit defaultdict.
from collection import defaultdict
def prime_factorization_1(num):
if num <= 1:
return False
else:
num_sqrt = math.floor(math.sqrt(num))
prime_list = make_prime_list_2(num_sqrt)
dict_counter = defaultdict(int)
for prime in prime_list:
while num % prime == 0:
dict_counter[prime] += 1
num //= prime
if num != 1:
dict_counter[num] += 1
dict_counter = dict(dict_counter)
return dict_counter
Implementierung ohne defaultdict.
def prime_factorization_2(num):
if num <= 1:
return False
else:
num_sqrt = math.floor(math.sqrt(num))
prime_list = make_prime_list_2(num_sqrt)
dict_counter = {}
for prime in prime_list:
while num % prime == 0:
if prime in dict_counter:
dict_counter[prime] += 1
else:
dict_counter[prime] = 1
num //= prime
if num != 1:
if num in dict_counter:
dict_counter[num] += 1
else:
dict_counter[num] = 1
return dict_counter
Die Geschwindigkeit ändert sich nicht mit oder ohne Standarddiktat.
%timeit prime_factorization_1(random.randrange(10 ** 5))
%timeit prime_factorization_2(random.randrange(10 ** 5))
10000 loops, best of 3: 33.6 µs per loop
10000 loops, best of 3: 33.2 µs per loop
Das Produkt jeder (Anzahl der Fraktionen + 1) der Primfaktorisierung ist die Anzahl der Fraktionen.
Implementierung ohne Primfaktorisierung.
def search_divisor_num_1(num):
if num < 0:
return None
elif num == 1:
return 1
else:
num_sqrt = math.floor(math.sqrt(num))
prime_list = make_prime_list_2(num_sqrt)
divisor_num = 1
for prime in prime_list:
count = 1
while num % prime == 0:
num //= prime
count += 1
divisor_num *= count
if num != 1:
divisor_num *= 2
return divisor_num
Implementierung unter Verwendung der oben implementierten Primfaktor-Zerlegung.
def search_divisor_num_2(num):
if num < 0:
return None
elif num == 1:
return 1
else:
divisor_num = 1
dict_fact = prime_factorization_1(num)
for value in dict_fact.values():
divisor_num *= (value + 1)
return divisor_num
Beim Vergleich der Geschwindigkeit gibt es keinen großen Unterschied.
%timeit search_divisor_num_1(random.randrange(10 ** 5))
%timeit search_divisor_num_2(random.randrange(10 ** 5))
10000 loops, best of 3: 33.5 µs per loop
10000 loops, best of 3: 34.1 µs per loop
Um ehrlich zu sein, wird dies nur durch num / 2 geteilt, daher denke ich, dass es schneller geht, es einfach zu machen.
def make_divisor_list(num):
if num < 1:
return []
elif num == 1:
return [1]
else:
divisor_list = []
divisor_list.append(1)
for i in range(2, num // 2 + 1):
if num % i == 0:
divisor_list.append(i)
divisor_list.append(num)
return divisor_list
%timeit make_divisor_list(random.randrange(10 ** 5))
1000 loops, best of 3: 1.94 ms per loop
Wenn Sie auf den Boden treten, wird die Bestellung ziemlich groß und läuft über. Implementierung mit Memorandum, um dies zu vermeiden.
def search_divisor_num_of_factorial_num(num):
if num <= 0:
return 0
elif num == 1 or num == 2:
return 1
else:
#Geben Sie die Primzahlen und ihre Zahlen ein
dict_counter = defaultdict(int)
#Diktat für Notizen
dict_memo = defaultdict(list)
for a_num in range(2, num + 1):
num_sqrt = math.ceil(math.sqrt(a_num))
prime_list = make_prime_list_2(num_sqrt)
#Behalten Sie den Schlüssel, um das Diktat für das Memo einzugeben
now_num = a_num
for prime in prime_list:
while a_num % prime == 0:
#Wenn es im Memo enthalten ist, verschieben Sie alles von dort und verlassen Sie die Schleife, wenn Sie fertig sind
if a_num in dict_memo:
for memo in dict_memo[a_num]:
dict_counter[memo] += 1
dict_memo[now_num].append(memo)
a_num = 1
else:
dict_counter[prime] += 1
dict_memo[now_num].append(prime)
a_num //= prime
if a_num != 1:
dict_counter[a_num] += 1
dict_memo[now_num].append(a_num)
divisor_num = 1
dict_fact = dict(dict_counter)
for value in dict_fact.values():
divisor_num *= (value + 1)
return divisor_num
Vergleich mit dem Fall, in dem die Leistung auf die Funktion geworfen wird, um die Anzahl der obigen Brüche zu ermitteln.
math.factorial(10) #Im Falle von
3628800
%timeit search_divisor_num_1(math.factorial(10))
%timeit search_divisor_num_of_factorial_num(10)
1000 loops, best of 3: 331 µs per loop
10000 loops, best of 3: 28.2 µs per loop
math.factorial(50) #Im Falle von
30414093201713378043612608166064768844377641568960512000000000000
%timeit search_divisor_num_1(math.factorial(50))
%timeit search_divisor_num_of_factorial_num(50)
Overflow
1000 loops, best of 3: 177 µs per loop
Ich weiß, dass SciPy ein Modul hat, das Primzahlen verarbeitet, aber es ist keine Standardbibliothek, und ... Es wäre schön, der Standardbibliothek eine Bibliothek hinzuzufügen, die Primzahlen und Brüche verarbeiten kann.
Recommended Posts