用大數字進行Python優化

我想打印所有素數，連續7個小於10000000000。當使用range()時，我得到一個MemoryError，因爲生成的數組無法存儲，所以我將該循環更改爲while循環。用大數字進行Python優化

但是這個程序真的很慢。打印找到的第一個號碼需要一分多鐘。

import math 

def is_prime(n): 
    if n % 2 == 0 and n > 2: 
     return False 
    i = 3 
    while i < math.sqrt(n) + 1: 
    #for i in range(3, int(math.sqrt(n)) + 1, 2): 
     if n % i == 0: 
      return False 
     i += 2 
    return True 

def is_super_happy(n): 
    count = 0 
    while n != 0: 
     if n%10 == 7: 
      count += 1 
      if count == 7: 
       return True 
     else: 
      count = 0 
     n /= 10 
    return count == 7 

i = 7777777 
while i < 10e10: 
#for i in range(7777777, int(10e10)): 
    if is_super_happy(i) and is_prime(i): 
     print i 
    i += 1

我不能想到任何事情都可以讓這件事變得更快，我希望它變得非常快。

任何想法，提示？

來源

2014-11-04 dabadaba

你可以使用多利用其他CPU內核。 – 2014-11-04 15:06:23

不要使用'while'，而是使用'xrange'而不是'range'（在Python 3中使用'range'） – Unapiedra 2014-11-04 15:09:27

提示：你的數字都是十位數。其中7個是連續7次。有多少數字需要考慮？ – RemcoGerlich 2014-11-04 15:15:47

兩個建議：

生成7,8和9位數字小於10e10直接含有7777777（而不是檢查每一個號碼反過來），然後檢查它們。這些數字相對較少。

例如，這裏的生成所有這樣的數字，其年底與「7777777」列表的方式： [int(str(x)+'7777777') for x in xrange(100)]
考慮使用概率測試檢查素性（如Miller-Rabin）。這告訴你x是否是一個非常高的可能性的素數，並且更快地檢查可能數千個小於x的數字。

來源

2014-11-04 15:18:16

以及我應該如何直接生成這些數據而不檢查數字是否確實包含「7777777」？ – dabadaba 2014-11-04 15:35:30

@dabadaba - 我編輯了我的答案，包括一個建議。 – 2014-11-04 15:41:40

您目前的算法非常浪費：is_prime在每次迭代中檢查每個數字從1到sqrt(n)，而它應該只檢查已知的素數。

修改你的算法，使其實現http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes

此外，你在你的while循環的每一個節拍計算sqrt(n)（可能幾百萬次，如果你有足夠高），但它不會改變。在函數的開始處計算一次並重用該函數。

來源

2014-11-04 15:09:19

當存儲算法使用的布爾列表時，我得到一個'MemoryError'。 – dabadaba 2014-11-04 15:31:23

考慮使用更高效的內存數據結構（numpy數組，也許？）。 Python列表非常浪費（基本結構約爲36個字節，其中包含的每個bool約4個字節）。另外，如果還不是這種情況，則使用64位Python（32位僅限於2個內存）。 – 2014-11-04 15:36:27

我嘗試使用numpy數組，我仍然收到內存錯誤。 – dabadaba 2014-11-05 09:37:26

我在大約四分之一秒內發現了250個素數，我不想給我的代碼，因爲你的問題看起來像作業。

方法：

第一，找到低於100 000的所有素數（這是開方（你的最大數量）），用篩子。
is_prime（）只需檢查是否有任何素數會將
除以這些數字中只有4000個;考慮數字000到999.他們可以用四種方式與7777777結合;說123變成7777777123，1777777723,1277777773和1237777777.生成這些，檢查它們是否符合素數，完成。
使用字符串（）或只是數學（12 * 100000000 + 7777777×10 + 3）生成的數字

來源

2014-11-04 15:37:48 RemcoGerlich

用大數字進行Python優化

回答

相關問題