python - 用于查找素数因子的 python 代码中的语法错误。如果有人可以帮助我，我将不胜感激

Question

我一直在使用进行素数分解的代码时遇到语法错误

这是这个代码

from sys import argv
from os import system, get_terminal_size
from math import sqrt

number = int(argv[1])
width = get_terminal_size().columns
prime_numbers = []
prime_factors = []
_ = system('clear')
print() 

def is_prime(n):
    for i in range(2, n):
        if n % i == 0:
            return False

    return True

if is_prime(number):
    print(f"It is a prime number \nIts only factors are 1 and itself \n1, {number}")
    exit()

x = len(str(number))
for i in range(2, int(sqrt(number))):
    if is_prime(i):
            prime_numbers.append(i)

            #print(f"found ")
#print(prime_numbers)

i = 0
while True:
    if (number % prime_numbers[i] != 0):
        i += 1
        continue
    
    prime_factors.append(prime_numbers[i])
    print("%2d  | %3d".center(width) % (prime_numbers[i], number))
    print("_________".center(width))                                
    number /= prime_numbers[i]
    if number == 1:
        break
print("1".center(width))

print("Answer ")

i = len(prime_factors)
j = 1

for k in prime_factors:
    if j == i:
        print(k)
        break

    print(f"{k}", end=" X ")
    j += 1

这适用于小于 4 或 5 位的小数字，但对于较大的数字会产生索引错误。如果我删除第 24 行的 sqrt 函数，它开始花费的时间太长。

错误看起来像这样

Traceback (most recent call last):
  File "prime-factor.py", line 33, in <module>
    if (number % prime_numbers[i] != 0):
IndexError: list index out of range

real    0m0.049s
user    0m0.030s
sys 0m0.014s
(base) Souravs-MacBook-Pro-5:Fun-Math-Algorithms aahaans$ time python3 prime-factor.py 145647

我无法解决此问题，如果您能帮助我，我将不胜感激。

标签： pythonalgorithm

Answer 1

代码有两个基本问题。对于素数的 for 循环之一，您必须检查直到 int(sqrt(number))+1。并且，在那之后的while循环中，当数字低于原始数字的sqrt时，您必须中断，应该使用另一个变量。更正后的代码是：

from sys import argv
from os import system, get_terminal_size
from math import sqrt

number = int(argv[1])
width = get_terminal_size().columns
prime_numbers = []
prime_factors = []
_ = system('clear')
print() 

def is_prime(n):
  for i in range(2, n):
    if n % i == 0:
      return False

  return True

if is_prime(number):
  print(f"It is a prime number \nIts only factors are 1 and itself \n1, {number}")
  exit()

x = len(str(number))
limit = int(sqrt(number))
for i in range(2, limit+1):
  if is_prime(i):
    prime_numbers.append(i)

i = 0
while True:
  if i == len(prime_numbers)-1:
    # prime_factors.append(int(number))
    break
  if (number % prime_numbers[i] != 0):
    i += 1
    continue
  prime_factors.append(prime_numbers[i])
  print("%2d  | %3d".center(width) % (prime_numbers[i], number))
  print("_________".center(width))                                
  number /= prime_numbers[i]
prime_factors.append(int(number))
print("%2d  | %3d".center(width) % (number, number))
print("_________".center(width))
print("1".center(width))

print("Answer ")
i = len(prime_factors)
j = 1
for k in prime_factors:
  if j == i:
    print(k)
    break
  print(f"{k}", end=" X ")
  j += 1

如果我的解释不清楚，请查看代码中的更改。