J'utilise souvent des nombres premiers et des fractions en python, mais je l'ai écrit parce qu'il n'y avait pas de bibliothèque qui gère les nombres premiers et les fractions.
Il existe des "divisions d'essai" et des "tamis d'ératostines" comme anciens algorithmes pour le jugement des nombres premiers et l'énumération des nombres premiers.
Implémentation considérée à partir de la définition des nombres premiers. Renvoie True s'il n'est pas divisible par un entier supérieur ou égal à 2 et inférieur ou égal à $ \ sqrt {num} $.
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
Mise en œuvre à l'aide de la division d'essai.
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 nombre premier(Nombres non divisibles par 2, 3 ou 5)Se diviser les uns après les autres
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
En comparant la vitesse d'exécution, la division d'essai est certainement plus rapide.
%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
Implémentation utilisant le jugement de nombre premier implémenté ci-dessus
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 avec un tamis Eratostenes.
def make_prime_list_2(num):
if num < 2:
return []
#0 n'est pas un nombre premier
prime_list = [i for i in range(num + 1)]
prime_list[1] = 0 #1 n'est pas un nombre premier
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]
Comparez les vitesses d'exécution. Le tamisage des ératostènes est plus rapide.
%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
À propos, il est extrêmement lent de préparer d'abord une table de nombres premiers et d'effectuer un jugement sur les nombres premiers.
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
Vous pouvez trouver le nombre de fractions en utilisant la factorisation première.
Implémentation à l'aide de 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
Implémentation sans 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
La vitesse ne change pas avec ou sans defaultdict.
%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
Le produit de chaque (nombre de fractions + 1) de la factorisation première est le nombre de fractions.
Implémentation sans factorisation prime.
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
Implémentation utilisant la décomposition en facteurs premiers implémentée ci-dessus
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
Il n'y a pas beaucoup de différence en comparant la vitesse.
%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
Pour être honnête, cela n'est divisé que par num / 2, donc je pense que c'est plus rapide de le faire facilement.
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
Lorsque vous marchez sur le sol, la commande devient assez importante et déborde. Mise en œuvre à l'aide de mémorandum pour l'éviter.
def search_divisor_num_of_factorial_num(num):
if num <= 0:
return 0
elif num == 1 or num == 2:
return 1
else:
#Entrez les nombres premiers et leurs nombres
dict_counter = defaultdict(int)
#Dict pour notes
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)
#Gardez la clé à mettre dans le dict pour mémo
now_num = a_num
for prime in prime_list:
while a_num % prime == 0:
#Si c'est dans le mémo, déplacez tout à partir de là et quittez la boucle lorsque vous avez terminé
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
Comparaison avec le cas où la puissance est jetée telle quelle à la fonction pour trouver le nombre des fractions ci-dessus.
math.factorial(10) #dans le cas de
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) #dans le cas de
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
Je sais que SciPy a un module qui gère les nombres premiers, mais ce n'est pas une bibliothèque standard, et ... Ce serait bien d'ajouter une bibliothèque capable de gérer les nombres premiers et les fractions à la bibliothèque standard.
Recommended Posts