Nombres premiers et fractions

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.

Jugement des nombres premiers et énumération des nombres premiers

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.

Jugement du nombre premier

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

Énumération des nombres premiers

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

Factorisation et réduction prime

Vous pouvez trouver le nombre de fractions en utilisant la factorisation première.

Factorisation prime

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

Nombre d'environ

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

Énumérer sur les nombres

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

Nombre de fractions du multiplicateur de plancher

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

Nombres premiers et fractions
Discrimination des nombres premiers
Trouver des nombres premiers récursivement
Nombre premier en Python
Le nombre premier de cette année
Juger les nombres premiers avec python
Implémentation de Fibonacci et des nombres premiers (python)
Tri avec un mélange de chiffres et de lettres
Projet Euler 10 "Somme des nombres premiers"
C'est un nombre premier ... Comptez les nombres premiers ...
[Python] nCr mod Calculer les nombres premiers
Agrégation et visualisation des nombres accumulés
J'ai cherché un nombre premier avec python
Résoudre avec Ruby et Python AtCoder ABC084 D Somme cumulative des nombres premiers