[PYTHON] [Pour les professionnels de la concurrence] Résumé des facteurs premiers, des réductions et des facteurs premiers

Jugement du nombre premier

Vous n'avez qu'à rechercher √N pour juger s'il est divisible.
Lorsque N = a * b (a <= b) est défini, s'il peut être déterminé qu'il est divisible par ʻa, il n'est pas nécessaire de déterminer s'il est divisible par b`.
En d'autres termes, il suffit de juger s'il peut être divisé jusqu'au cas de ʻa = bau maximum, il suffit donc de regarder a qui satisfaitN = a * b = a * a = a ** 2` ..
O(√N)

#Jugement du nombre premier
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):
        #Regardez ci-dessous √N. je*Je le compare comme i parce que je ne veux pas gérer les fractions.
        if i * i > n:
            return True
        if n % i == 0:
            return False

#Jugement du nombre premier
N = 7
print(isPrime(N))
# True

Dénombrement des nombres premiers / tamis Eratostenes

Préparez une liste jusqu'à N, et si vous en trouvez une qui correspond à un nombre premier, supprimez le multiple.
Comme ci-dessus, jusqu'à √N est OK
La suppression multiple est effectuée à partir de ʻi ** 2parce que ʻi * (i -1)a été éliminé dans le processus précédent.

Par exemple.) Quand ʻi = 5`, "5 * 2", "5 * 3" et "5 * 4" sont tous supprimés comme des multiples de 2, des multiples de 3 et des multiples de 2.

#Tamis Eratostenes
#Énumération des nombres premiers(La section peut être spécifiée)
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)    #Que ce soit un nombre premier
    #0 et 1 à Faux
    isPrime[0] = isPrime[1] = False
    for i in range(2, int(last ** 0.5 + 1)):
        if isPrime[i]:
            #Tamiser. Définissez tous les multiples de i sur False. En ce moment je^Vous n'avez pas besoin d'en voir jusqu'à 2 car il a déjà été exclu
            for j in range(i ** 2, last + 1, i):
                isPrime[j] = False
    return [i for i in range(first, last + 1) if isPrime[i]] 

#Énumération des nombres premiers
N = 10  #Y compris le dernier numéro
print(getPrimes(N))
# [2, 3, 5, 7]

#Énumération des nombres premiers
F = 13
L = 23  #Y compris le dernier numéro
print(getPrimes(F, L))
# [13, 17, 19, 23]

#Nombre de nombres premiers
N = 10 ** 7
print(len(getPrimes(N)))
# 664579
# 2.Environ 5 s

Énumérer sur les nombres

Code pour énumérer les fractions à grande vitesse (Python) Je l'ai utilisé comme référence. Il sort trié.

#Énumérer sur les nombres
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]
    
#Énumérer sur les nombres
N = 120
print(getDivisors(N))
# [1, 2, 3, 4, 5, 6, 8, 10, 12, 15, 20, 24, 30, 40, 60, 120]

Obtention du nombre de réductions pour plusieurs entiers (une autre méthode)

Vous pouvez répéter de 1 à N pour obtenir la fraction avec le code ci-dessus et calculer à partir de la longueur de la liste, mais une autre méthode.
Boucle sur le côté de la fraction et compte ceux avec cette fraction.
À ce stade, si la fraction elle-même est incluse dans la liste, il semble qu'une liste de fractions puisse être obtenue en une seule fois pour plusieurs entiers.
O (NlogN). L'énumération est stricte si elle vaut 10 ^ 7.

#Obtenez le nombre d'environ
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


#Obtenez le nombre d'environ
N = 10
print(getNumsOfDivisorsOfEachNumbers(N))

Référence) ABC172 D problème d'AtCoder

Factorisation prime

Vous pouvez le diviser calmement, mais c'est une méthode utile lorsque vous souhaitez trouver les facteurs premiers pour plusieurs nombres en même temps que ci-dessus.
Lors de la suppression de multiples sur le tamis Eratostenes, au lieu de les gérer avec des drapeaux, décrivez par quel nombre ils ont divisé afin qu'ils puissent être tracés après de.
Obtenez les facteurs premiers d'une manière similaire au doublement.

ex.) Par exemple, lors de la factorisation de 10 en facteurs premiers.

Voir 10 dans la liste.
Puisque 10 peut être divisé par 2, ajoutez 2 à la liste des facteurs premiers.
A partir de 10/2 = 5, voyez le lieu correspondant à 5 de récréation. 4.5 s'écrit 5 et est connu comme un nombre premier, donc le jugement est terminé.

import time

#Factorisation prime
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)]      #Le plus petit nombre premier qui divise le nombre i
    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:             #Si vous supprimez la condition et autorisez l'écrasement, les facteurs premiers obtenus seront dans l'ordre décroissant.
                    dividableMinimunPrime[j] = i
    #Procédez de la même manière que pour doubler
    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]

Référence) Problème AtCoder ABC152 E