大数的质因数
prime factors for large numbers
我写这篇文章是为了确定任何给定数字的最大质因数。它适用于少于 9 位数的数字,但当位数超过 9 时,它的行为不确定。我该如何优化它?
此函数判断一个数是否为质数
def is_prime(x):
u = 1
i = 2
while i < x:
if x%i == 0:
u = 0
break
else:
i = i+1
return u
此函数确定一个数是否是另一个数的质因数
def detprime(x,y):
if x%y == 0:
if (is_prime(y)):
return 1
else:
return 0
else:
return 0
此部分检查给定数字的所有质因数,将它们存储在列表中,returns 最大值
def functionFinal(x):
import math
factors = []
y = x//2
for i in range(1,y):
if detprime(x,i) == 1:
factors.append(i)
y = len(factors)
print(factors[y-1])
import time
start_time = time.process_time()
print("Enter a number")
num = int(input())
functionFinal(num)
打印(time.process_time()-start_time)
您可以通过使用更有效的函数来检查素数来改进您的代码。除此之外,您只需要存储列表的最后一个元素 factors
。此外,您可以通过 JIT 编译函数和使用并行化来提高速度。在下面的代码中,我使用 numba.
import math
import numba as nb
@nb.njit(cache=True)
def is_prime(n):
if n % 2 == 0 and n > 2:
return 0
for i in range(3, int(math.sqrt(n)) + 1, 2):
if n % i == 0:
return 0
return 1
@nb.njit(cache=True)
def detprime(x, y):
if x % y == 0:
if (is_prime(y)):
return 1
else:
return 0
else:
return 0
@nb.njit(parallel=True)
def functionFinal(x):
factors = [1]
y = x // 2
for i in nb.prange(1, y): # check in parallel
if detprime(x, i) == 1:
factors[-1] = i
return factors[-1]
所以,那个
functionFinal(234675684)
有性能比较,
Your code : 21.490s
Numba version (without parallel) : 0.919s
Numba version (with parallel) : 0.580s
HTH.
我写这篇文章是为了确定任何给定数字的最大质因数。它适用于少于 9 位数的数字,但当位数超过 9 时,它的行为不确定。我该如何优化它?
此函数判断一个数是否为质数
def is_prime(x):
u = 1
i = 2
while i < x:
if x%i == 0:
u = 0
break
else:
i = i+1
return u
此函数确定一个数是否是另一个数的质因数
def detprime(x,y):
if x%y == 0:
if (is_prime(y)):
return 1
else:
return 0
else:
return 0
此部分检查给定数字的所有质因数,将它们存储在列表中,returns 最大值
def functionFinal(x):
import math
factors = []
y = x//2
for i in range(1,y):
if detprime(x,i) == 1:
factors.append(i)
y = len(factors)
print(factors[y-1])
import time
start_time = time.process_time()
print("Enter a number")
num = int(input())
functionFinal(num)
打印(time.process_time()-start_time)
您可以通过使用更有效的函数来检查素数来改进您的代码。除此之外,您只需要存储列表的最后一个元素 factors
。此外,您可以通过 JIT 编译函数和使用并行化来提高速度。在下面的代码中,我使用 numba.
import math
import numba as nb
@nb.njit(cache=True)
def is_prime(n):
if n % 2 == 0 and n > 2:
return 0
for i in range(3, int(math.sqrt(n)) + 1, 2):
if n % i == 0:
return 0
return 1
@nb.njit(cache=True)
def detprime(x, y):
if x % y == 0:
if (is_prime(y)):
return 1
else:
return 0
else:
return 0
@nb.njit(parallel=True)
def functionFinal(x):
factors = [1]
y = x // 2
for i in nb.prange(1, y): # check in parallel
if detprime(x, i) == 1:
factors[-1] = i
return factors[-1]
所以,那个
functionFinal(234675684)
有性能比较,
Your code : 21.490s
Numba version (without parallel) : 0.919s
Numba version (with parallel) : 0.580s
HTH.