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

Primality test

#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

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.

image.png

#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)

#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

image.png

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

  1. See 10 in the list.
  2. Since 10 can be divided by 2, add 2 to the prime factor list and add
  3. 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

Recommended Posts

[For competition professionals] Prime number, divisor, prime factorization summary
Binary search summary for competition professionals
[For competition professionals] Run-length compression summary
[For competition professionals] Summary of doubling
[For competition professionals] Minimum spanning tree summary
[For competition professionals] Union Find Tree Summary
Prime number
[For competition pros] Priority queue (heapq) Summary
Benchmark for C, Java and Python with prime factorization
Divisor enumeration when prime factorization is already known (Python)