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`.at the maximum, so it is sufficient to look at a that satisfies
N = a * b = a * a = a ** 2`. ..#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
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
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]
#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
eg.) For example, when factoring 10 into prime factors.
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