Python Project Euler 3

Question

Je suis novice en python, j'essaie d'aider ma copine à apprendre le codage à travers le projet Euler, j'ai suggéré qu'elle commence par python. Malheureusement sur le problème 3 nous sommes arrivés à une erreur étrange. Pour trouver les facteurs premiers de nombres plus petits, cela semble fonctionner, mais en essayant de trouver les facteurs premiers de 600851475143, il s'étouffe. J'ai eu l'impression que python était extrêmement indulgent pour les valeurs entières maximales, donc je ne sais pas pourquoi cela ne fonctionne pas ici.

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

n = 600851475143 

for i in range (1, n) : 
    if n % i == 0 : 
     if is_prime (i) == 1 : 
      print i 

Si quelqu'un pouvait me guider, je serais très reconnaissant!

David

edit: Je sais bien comment tout cela est sous-optimale!

Answer 1

Comme personne ne répondait à l'évidence, utilisez xrange au lieu de range:

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

n = 600851475143 

for i in xrange (1, n) : 
    if n % i == 0 : 
     if is_prime (i) == 1 : 
      print i 

Mais gardez à l'esprit c'est toujours très lent, mais vous ne rencontrerez pas MemoryErrors.

Answer 2

voir cet algorithme pour passer par des chiffres en divisant les facteurs, il est plus efficace:

while num > 1: 
    if num % div == 0: 
     num /= div 
     div -= 1 
    div += 1 

Answer 3

Trouver les facteurs premiers de grands nombres ne sont pas une chose triviale. La criptographie est basée sur des clés qui sont le produit de deux clés assez grandes pour que les plus gros ordinateurs parallèles s'étouffent. Quand il y a une amélioration de la puissance ou des méthodes de calcul, il suffit d'utiliser de plus gros nimbers pour le garder en sécurité,

La division d'essai chie très rapidement, Pour les plus grands nombres il y a des méthodes d'essai et d'erreur comme celles de Brent qui peuvent aller plus loin.
Le code que j'ai attaché a trouvé 600851475143 = [71, 839, 1471, 6857] en 0,1 seconde, mais il étouffe de la même manière pour les plus grands nombres.
Il utilise la division d'essai jusqu'à 1M puis passe à la méthode de Brent.
Je ne peux pas expliquer Brent, Je viens de copier le code ...

#Py3.4 

from fractions import gcd 
from random import randint 
from time import clock 

def brent(N): 
    # brent returns a divisor, not guaranteed to be prime 
    if N%2==0: return 2 
    y,c,m = randint(1, N-1),randint(1, N-1),randint(1, N-1) 
    g,r,q = 1,1,1 
    while g==1:    
     x = y 
     for i in range(r): 
      y = ((y*y)%N+c)%N 
     k = 0 
     while (k<r and g==1): 
      ys = y 
      for i in range(min(m,r-k)): 
      y = ((y*y)%N+c)%N 
      q = q*(abs(x-y))%N 
      g = gcd(q,N) 
      k = k + m 
     r = r*2 
    if g==N: 
     while True: 
      ys = ((ys*ys)%N+c)%N 
      g = gcd(abs(x-ys),N) 
      if g>1: break 
    return g 

def factorize(n1): 
    if n1<=0: return [] 
    if n1==1: return [1] 
    n=n1 
    b=[] 
    p=0 
    mx=1000000 
    while n % 2 ==0 : b.append(2);n//=2 
    while n % 3 ==0 : b.append(3);n//=3 
    i=5 
    inc=2 
    while i <=mx: 
     while n % i ==0 : b.append(i); n//=i 
     i+=inc 
     inc=6-inc 
    while n>mx: 
     p1=n 
     #iterate until divisor is prime 
     while p1!=p: 
      p=p1 
      p1=brent(p) 
      print(p1) 
     b.append(p1);n//=p1 
    if n!=1:b.append(n) 
    b.sort() 
    return b 


from functools import reduce 
from sys import argv 
def main(): 
    if len(argv)==2: 
    n=int(argv[1]) 
    else: 
    n=int(eval(input(" Integer to factorize? "))) 
    t1=clock() 
    li=factorize(n) 
    print (n,"= ",li) 
    print(clock()-t1, " seconds") 
    print ("n - product of factors = ",n - reduce(lambda x,y :x*y ,li)) 

if __name__ == "__main__": 
    main()