Python "OverflowError"

Question

Tôi chỉ mới bắt đầu học cách viết mã bằng Python. Tôi cố gắng để viết một số mã để trả lời câu này Câu hỏi Dự án Euler:

Các thừa số nguyên tố của 13.195 là 5, 7, 13 và 29.

các thừa số nguyên tố lớn nhất trong số 600.851.475.143 là gì?

Chương trình của tôi hoạt động với trường hợp thử nghiệm là 13195, nhưng khi tôi cố gắng nhập 600851475143, tôi nhận được lỗi: "Kết quả OverflowError: range() có quá nhiều mục" Có ai biết cách khắc phục sự cố này không?

Đây là mã của tôi:

class Euler3: 
    "A class to find the largest prime factor of a given number" 
    n = 600851475143 
    primeFactors = [] 
    for i in range(2,n): 
     if (n%i ==0): 
      primeFactors.append(i) 
      n = n/i 
      i = i -1 #reset i 
    print primeFactors 

Bất kỳ trợ giúp hoặc đề xuất sẽ được nhiều đánh giá cao!

Answer 1

Tôi đoán bạn đang sử dụng python 2 và không phải python 3 - range(2,n) thực sự tạo danh sách! Bạn không có đủ bộ nhớ để lưu trữ 600 tỷ con số! Tuy nhiên, xrange sẽ là tốt.

Ngoài ra, ý tưởng của bạn về i=i-1 không hoạt động. Đối với các vòng không hoạt động như C, và hack đó chỉ hoạt động trong các vòng kiểu C. Vòng lặp for lặp lại trên range(2,n). Nếu i nhận giá trị 5 cùng một lúc lặp lại, thì bất kể bạn làm gì với i, nó vẫn nhận được 6 vào lần sau.

Ngoài ra, danh sách range(2,n) được tạo khi bạn nhập vòng lặp. Vì vậy, khi bạn sửa đổi n, điều đó không thay đổi bất cứ điều gì.

Bạn sẽ phải suy nghĩ lại logic của mình một chút.

(nếu bạn không tin tôi, hãy thử sử dụng 175 như một trường hợp thử nghiệm)

Như một lời nhận xét cuối cùng, có lẽ bạn nên có thói quen sử dụng các bộ phận nguyên đặc biệt: n = n // i. Mặc dù / và // hoạt động tương tự trong python 2, đó thực sự là hành vi không được chấp nhận và chúng không hoạt động tương tự trong python 3, trong đó / sẽ cung cấp cho bạn số dấu chấm động.

Answer 2

Bạn có thể khắc phục vấn đề bằng cách sử dụng xrange thay vì range

vấn đề tiếp theo của bạn sẽ là những chương trình có cách quá dài để chạy vì bạn cần phải thoát ra khỏi vòng lặp theo một số điều kiện

Một cách tốt hơn để đối phó với các yếu tố lặp lại là để thay thế cho if với một while

 while (n%i ==0): 
     primeFactors.append(i) 
     n = n/i 

Answer 3

chức năng range tạo ra một danh sách và tr ies để lưu trữ nó trong bộ nhớ. Tạo một danh sách nhiều con số dài là những gì gây ra OverflowError. Thay vào đó, bạn có thể sử dụng xrange để nhận một trình tạo máy theo yêu cầu.

Điều đó nói rằng, tôi nghĩ bạn sẽ thấy rằng thuật toán của bạn quá chậm để tính toán số nguyên tố lớn. Có rất nhiều thuật toán số nguyên tố, nhưng tôi có thể đề nghị kiểm tra Sieve of Eratosthenes làm điểm bắt đầu.

CHỈNH SỬA: Đúng xrange thực sự không trả lại trình tạo, nhưng đối tượng xrange hoạt động rất giống máy phát. Tôi không chắc chắn nếu bạn quan tâm, nhưng nó đã làm tôi lo lắng rằng tôi đã không chính xác!

Answer 4

n = 600851475143 
primeFactors = [] 
for i in range(2,n): 

tôi nghĩ rằng bạn có thể tối ưu hóa các chức năng bởi nhận thấy rằng

for i in range(2,n): 

bạn có thể thay

range(2,n) 

bởi

range(2,int(sqrt(n))+2) 

vì, bạn có thể nhìn thấy wiki .. .

Answer 5

Tôi đã chiến đấu với Python "OverflowError", cũng như, làm việc trên dự án này. Nó đã khiến tôi phải cố gắng tìm ra một sự kết hợp có hiệu quả.

Tuy nhiên, tôi đã khám phá ra một thông minh, ít nhất tôi nghĩ vậy :), cách để làm điều đó.

Đây là mã của tôi cho sự cố này.

def IsNumberPrime(n): 
    bounds = int(math.sqrt(n)) 
    for number in xrange(2,bounds+2): 
     if n % number == 0: 
      return False 
    return True 

def GetListOfPrimeFactors(n): 
    primes = [] 
    factors = GetListOfFactors(n) 
    if n % 2 == 0: 
     primes.append(2) 

    for entries in factors: 
     if IsNumberPrime(entries): 
      primes.append(entries) 
    return primes 


GetListOfPrimeFactors(600851475143) 

def GetListOfFactors(n): 
    factors = [] 
    bounds = int(math.sqrt(n)) 
    startNo = 2 

    while startNo <= bounds: 
     if n % startNo == 0: 
     factors.append(startNo) 
     startNo += 1 
    return factors 

Điều tôi đã làm là lấy các yếu tố của số được nhập và nhập chúng vào danh sách "các yếu tố". Sau đó, tôi lấy danh sách các yếu tố và xác định những yếu tố nào là số nguyên tố và lưu trữ chúng vào một danh sách được in ra.

Tôi hy vọng điều này sẽ giúp

- Mike

Answer 6

Đây là cách tốt nhất để tìm số nguyên tố mà tôi đã tìm thấy cho đến nay:

def isprime(n): 
    #make sure n is a positive integer 
    n = abs(int(n)) 
    #0 and 1 are not primes 
    if n < 2: 
     return False 
    #2 is the only even prime number 
    if n == 2: 
     return True 
    #all other even numbers are not primes 
    if not n & 1: 
     return False 
    #range starts with 3 and only needs to go up to the square root of n 
    #for all odd numbers 
    for x in range (3, int(n**0.5)+1, 2): 
     if n % x == 0: 
      return False 
    return True #if it makes it through all the catches, it is a prime 

Answer 7

này đã cho tôi khoảng 5 giây để có được câu trả lời.

import math 

def is_prime_number(x): 
    for i in range(int(math.sqrt(x)), 2, -1): 
     if x % i == 0: 
     return False 
    return True 

def next_prime_number(number): 
    #Returns the next prime number. 
    if number % 2 == 0 and number != 2: 
     number += 1 
    while not is_prime_number(number): 
     number += 2 
    return number 

num = 600851475143 
i = 2 
while (i < long(math.sqrt(num)/2)): 
    if num % i == 0: 
     largest = i 
     print largest 
    i = next_prime_number(i + 1) 

Answer 8

xrange sẽ không thể giúp bạn (hoặc nó có thể!), Nhưng điều quan trọng ở đây là để reliaze mà bạn không cần phải tìm các số nguyên tố lên đến 600.851.475.143 hoặc các yếu tố của 600.851.475.143, nhưng đó là thừa số nguyên tố, vì vậy ... Sử dụng tốt phương pháp nguyên tố cũ, như vậy:

A=600851475143 
n=2 
fac=[] 
while(n<=int(A)): 
    B=1 
    while(A%n==0): 
     B=0 
     A=A/n 
    if(B==0): 
     fac.append(n) 
    n=n+1 

print max(fac) 

này sẽ trở lại với yếu tố chính argest gần như ngay lập tức