在python中處理任意大數字

爲了進一步提高編程技巧，我正在通過項目Euler進行工作。我重新審視我的代碼的問題3.在此之後遇到一個有趣的問題是我的代碼：在python中處理任意大數字

# prime numbers are only divisible by unity and themselves 
# (1 is not considered a prime number by convention) 
def isprime(n): 
    '''check if integer n is a prime''' 
    # 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 the squareroot 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 


try: 
    num = int(input('Please input a natural number:')) 
except ValueError: 
    print("Erm.. No. I need a number.") 


mylist = [] 
check = True 
newnum = num 
i= 0 


if isprime(num): 
    print("%r is a prime number."%num) 

else: 
    while check: 
     if isprime(i): 
      if newnum % i ==0: 
       mylist.append(i) 
       print("%r is a prime factor of %r"%(i,num)) 
       newnum = newnum/i 
       i=0 

       if newnum ==1: 
        check = False 

     if i==num: 
      print("I guess the program broke.") 
      check = False 
     i+=1 

    print ("The largest prime factor for %r is:"%num) 
    print (max(mylist)) 
    print ("The list of prime factors for %r is:"%num) 
    print (mylist)

所以我跑進問題是這樣的代碼將與超過17位長的數字永遠運行下去（我懷疑任何更高比144155188075855872這是2^59;它適用於一些18位數字而不是其他）。

我發現，如果我輸入一個高於該數字的數字並用Windows計算器檢查答案，答案將非常接近整數，但它將有一個小數部分。

如何更改我的函數以接受和正確計算任意大的數字？（最好不使用非標準文庫）

謝謝！

來源

2013-10-25 user2785724

你是什麼意思的「正確」？你使用Python 2嗎？還是3？ –

@StefanoSanfilippo我會從'print'函數和int（輸入（'而不是'int（raw_input（'。 – rlms

）'）中假定Python 3.x可能是這樣，但它們都是Python 2中的有效語句。 –

Python整數是任意精度的。我在你的代碼可能不會以高精確度工作唯一看到的是這樣的浮點計算：

int(n**0.5)+1

由於彩車是近似的，你會得到四捨五入誤差比64位浮點更大的數字可以精確地表示（發生在2點到50點左右）。相反，使用整數計算：

for x in itertools.count(3, 2): 
    if x > n ** 2: 
     break 
    if n % x == 0: 
     return False

來源

2013-10-25 20:09:45

或者你的意思是'x ** 2> n'？ –

你可以使用'takewhile'和'any'來擺脫顯式循環，我不確定它是否更易讀，或者是否小性能優勢將會更加顯着，但它可能是這樣的 – abarnert

從一個快速測試中，itertools版本在CPython 3.3.2中似乎快了大約2％，在PyPy 2.1.0b3/3.2.3中慢了12％，所以......從來沒有無論你認爲哪一個更容易閱讀，哪一個更好。用'不是n％x'代替'x * x> n'和'n％x == 0'的'x ** 2> n'（並且在itertools版本，'任何（n％x == 0 ...）''不全部（n％x ...）'）都有更大的區別。 – abarnert

在python中處理任意大數字

回答

相關問題