Ошибка синтаксиса в коде 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 цифр, но дает ошибка индекса для больших. Если я удалю функцию sqrt в строке 24, это займет слишком много времени.

Ошибки выглядят так

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

Я не могу решить эту проблему, я буду признателен, если вы можете помочь я

Answer 1

Есть две основные c проблемы с кодом. Один с for l oop для простых чисел, вы должны проверять до int (sqrt (number)) + 1. И, в то время как l oop после этого, вы должны прервать, когда число меньше 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

Если мое объяснение непонятно, посмотрите изменения в коде.

Answer 2

Я написал механизм факторизации малых чисел, который может множить числа.

import math

def LLL(N):
   p = 1<<N.bit_length()-1
   if N == 2:
     return 2
   if N == 3:
     return 3
   s = 4
   M = pow(p, 2) - 1
   for x in range (1, 100000):
     s = (((s * N ) - 2 )) % M
     xx = [math.gcd(s, N)] + [math.gcd(s*p+x,N) for x in range(7)] + [math.gcd(s*p-x,N) for x in range(1,7)] 
     try:
        prime = min(list(filter(lambda x: x not in set([1]),xx)))
     except:
        prime = 1
     if prime == 1:
        continue
     else:
        break
   #print (s, x, prime, xx)
   return prime

Фактор:

Я также заставил движок Alpertons ECM SIQs работать в python, если хотите факторизация при этом (уровень более 60 цифр):

https://github.com/oppressionslayer/primalitytest

Answer 3

Нет необходимости перестраивать то, что уже доступно primePy

from primePy import primes
primes.factors(101463649)

вывод

[7, 23, 73, 89, 97]