用大数字进行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优化

回答

相关问题