Python Code Acceleration Approach
I thought it was a fast way to write Python, so I inadvertently saw it, so I can't help but be worried. I won't write the environment because it doesn't make sense unless it gets faster in many environments.
import math
def is_prime(x : int) -> bool:
if x <= 1:
return False
if x % 2 == 0:
return x == 2
upper = math.floor(math.sqrt(x)) + 1
for i in range(3, upper, 2):
if x % i == 0:
return False
return True
def minimum_prime_number(x : int):
maxx = 10 ** 14 + 32
for i in range(x, maxx):
if is_prime(i):
return i
if __name__ == '__main__':
result = minimum_prime_number(100000000000000)
print(result)
100000000000031
0.504 seconds
We will add a probabilistic judgment method, but it will not change much.
def miller_rabin_test(n : int) -> bool:
k = 50
if n <= 1:
return False
if n % 2 == 0:
return n == 2
if n % 3 == 0:
return n == 3
if n % 5 == 0:
return n == 5
s, d = 0, n-1
while d % 2 == 0:
s, d = s+1, d>>1
while 0<k:
k = k-1
a = random.randint(1, n-1)
t, y = d, pow(a, d, n)
while t != n-1 and y != 1 and y != n-1:
y = pow(y, 2, n)
t <<= 1
if y != n-1 and t % 2 == 0:
return False
return True
def is_prime(x : int) -> bool:
if False == miller_rabin_test(x):
return False
upper = math.floor(math.sqrt(x)) + 1
for i in range(3, upper, 2):
if x % i == 0:
return False
return True
100000000000031
0.501 seconds
The calculation cost has exceeded.
def is_prime(x : int) -> bool:
if False == miller_rabin_test(x):
return False
upper = math.floor(math.sqrt(x))
count = 5
step = 4
while count<=upper:
if x % count == 0:
return False
step = 6 - step
count += step
return True
100000000000031
0.569 seconds
I'm getting tired of it, so I'm done. If I call C ++, I can't do it because it means I can write it in C ++.
Recommended Posts