1
votes

Erreur de syntaxe dans le code python pour trouver les facteurs premiers. J'apprécierais si quelqu'un pouvait m'aider

Je reçois une erreur de syntaxe avec du code qui effectue la factorisation des nombres premiers

Voici ce code

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

Cela fonctionne pour les petits nombres, moins de 4 ou 5 chiffres mais donne une erreur d'index pour les plus gros. Si je supprime la fonction sqrt à la ligne 24, cela prend trop de temps.

Les erreurs ressemblent à ceci

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

Je ne parviens pas à résoudre ce problème, J'apprécierais si vous pouviez m'aider.

python algorithm

2 commentaires

Je suis surpris que votre code fonctionne dans certains scénarios. Votre prime_factors est initialisé comme une liste vide puis directement utilisé dans l'expression if (number% prime_numbers [i]! = 0): dans la boucle while. prime_numbers [0] sera certainement une erreur d'index hors limites car prime_numbers est vide.

L'erreur que vous avez publiée n'est pas une erreur de syntaxe. Vous augmentez également la valeur de i sans condition, et vous attendez à ce que prime_numbers [i] fonctionne.

3 Réponses :

0
votes

Pas besoin de reconstruire ce qui est déjà disponible primePy

[7, 23, 73, 89, 97]

sortie

from primePy import primes
primes.factors(101463649)

0 commentaires

0
votes

Il y a deux problèmes de base avec le code. Un avec la boucle for pour les nombres premiers, vous devez vérifier jusqu'à int (sqrt (nombre)) + 1. Et, dans la boucle while après cela, vous devez interrompre lorsque le nombre est inférieur à sqrt du nombre d'origine, pour lequel une autre variable doit être utilisée. Le code corrigé est:

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

Si mon explication n'était pas claire, regardez les changements dans le code.

0 commentaires

0
votes

J'ai écrit un moteur de factorisation de petits nombres qui peut factoriser les nombres.

In [219]: LLL(10142789312725007)                                                                                                                                                       
Out[219]: 100711423

from https://stackoverflow.com/questions/4078902/cracking-short-rsa-keys

Facteur:

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

J'ai aussi créé le moteur Alpertons ECM SIQs travaillez en python si vous voulez une factorisation à ce niveau (plus de 60 chiffres): https://github.com/oppressionslayer/ primalitytest

0 commentaires