[PYTHON] [For competition professionals] Prime number, divisor, prime factorization summary

Primality test

You only have to look up to √N to judge whether it is divisible.
When N = a * b (a <= b) is set, if it can be determined that it is divisible by ʻa, it is not necessary to determine whether it is divisible by b`.
In other words, it is sufficient to judge whether it can be divided up to the case of ʻa = bat the maximum, so it is sufficient to look at a that satisfiesN = a * b = a * a = a ** 2`. ..
O(√N)

#Primality test
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):
        #Look below √N. i*Compare as i because you don't want to deal with decimals.
        if i * i > n:
            return True
        if n % i == 0:
            return False

#Primality test
N = 7
print(isPrime(N))
# True

Prime number enumeration / Eratosthenes sieve

Prepare a list up to N, and if you find a prime number, delete the multiple.
Same as above, up to √N is OK
Multiple deletion is performed from ʻi ** 2 because ʻi * (i -1) has been eliminated in the previous process.

eg.) When ʻi = 5, 5 * 2, 5 * 3, and 5 * 4` are all dropped as multiples of 2, multiples of 3, and multiples of 2.

#Eratosthenes Sieve
#Prime number enumeration(Interval can be specified)
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)    #Whether it is a prime number
    #0 and 1 to False
    isPrime[0] = isPrime[1] = False
    for i in range(2, int(last ** 0.5 + 1)):
        if isPrime[i]:
            #Sieve. Set all multiples of i to False. At this time i^You don't need to see up to 2 as it has already been screened out
            for j in range(i ** 2, last + 1, i):
                isPrime[j] = False
    return [i for i in range(first, last + 1) if isPrime[i]] 

#Prime number enumeration
N = 10  #Including the last number
print(getPrimes(N))
# [2, 3, 5, 7]

#Prime number enumeration
F = 13
L = 23  #Including the last number
print(getPrimes(F, L))
# [13, 17, 19, 23]

#Number of prime numbers
N = 10 ** 7
print(len(getPrimes(N)))
# 664579
# 2.About 5s

Divisor enumeration

Code for enumerating divisors at high speed (Python) I used it as a reference. It comes out sorted.

#Divisor enumeration
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]
    
#Divisor enumeration
N = 120
print(getDivisors(N))
# [1, 2, 3, 4, 5, 6, 8, 10, 12, 15, 20, 24, 30, 40, 60, 120]

Obtaining the number of divisors for multiple integers (another method)

You can repeat from 1 to N to get the divisor with the above code and calculate it from the length of the list, but another method.
Loop on the divisor side and count those with that divisor.
At this time, if the divisor itself is included in the list, it seems that a list of divisors can be obtained in one shot for multiple integers.
O (NlogN). Enumeration is strict if it is 10 ^ 7.

#Get the number of divisors all at once
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


#Get the number of divisors all at once
N = 10
print(getNumsOfDivisorsOfEachNumbers(N))

Reference) ABC172 D problem of AtCoder

Prime factorization

You can divide it calmly, but it is a useful method when you want to find the prime factors for multiple numbers at the same time as above.
When deleting multiples on the Eratosthenes sieve, instead of managing them with flags, describe what number they divided by so that they can be traced after de.
Obtain prime factors in a way similar to doubling.

eg.) For example, when factoring 10 into prime factors.

See 10 in the list.
Since 10 can be divided by 2, add 2 to the prime factor list and add
From 10/2 = 5, see the place corresponding to 5 of recreation. 4.5 is written as 5, and it is known as a prime number, so the judgment is completed.

import time

#Prime factorization
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)]      #The smallest prime number that divides the number 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:             #If you delete the condition and allow overwriting, the prime factors obtained will be in descending order.
                    dividableMinimunPrime[j] = i
    #Proceed in the same way as doubling
    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]

Reference) AtCoder ABC152 E Problem