PythonTip >> 博文 >> python 学习

求一个范围内的素数

zihua 2013-12-19 10:12:58 点击: 863 | 收藏


学算法时候,求素数总是一道逃不掉的练习题。

好久没写算法相关的练习了,学习了python 就拿它来练一下手吧。

在求素数之前,首先我们了解一下 什么是素数。

按维基百科的说法是:

素数指在大于1的自然数中,除了1和此整数自身外,无法被其他自然数整除的数(也可定义为只有1和本身两个因数的数)

因此我们可以总结为以下几点:
1. 素数是自然数,且大于1
2. 素数只能被1和其本身整除
3. 最小的素数是2
4. 这也是由2延伸,素数一定时奇数,因为合数能比2整除

那么也就是说素数实际上是奇数的一个真子集,既然这样我们不妨从奇数里面把素数挑出来。

例如一个连续的奇数集合,我们需要把里面的素数找出来:

[3,5,7,9,11,13,15,17,19,21]

首先,判断一个数x是素数的方法是,分别用2 . . sqrt(x)去试除x,看能否被整除,一旦出现被整除的情况,那么说明x不是素数。若全部试除过都没被整除,说明x是素数。
eg:
   def isPrime(x):
       for i in range(2,math.sqrt(x)):
           if  x % i == 0:
               return 1
       return 0

事实上在用2 . . sqrt(x) 重复去试除x 是一个不合理的过程,在上面我们分析过,素数其实是奇数的一个真子集,那么肯定不能被2整除,那么用2、4、6、8等偶数去试除x其实是在做无用功,因此我们在试除时候其实是可以忽略除数是偶数的情况。我们可以作以下调整:
eg:
   def isPrime(x):
       if x % 2 == 0:
          return 1
       for i in range(3,math.sqrt(x),2):
           if  x % i == 0:
               return 1
       return 0
这样就省去了除数是偶数的情况。

另外,我们看一下合数的组成。

4=2*2,6=3*2,8=2*2*2,9=3*3,15 = 3*5

每个合数总是能分解为几个质因子,因此,我们拿合数作为除数去试除x时候也是不太合理的,也做了不少无用功,我们可以考虑优化。

首先合数可以分解为几个质因子(y= a*b*c 其中a、b、c都是素数),那么判断x是否能被y整除时候,实际上是判断x是否能分别被a,b,c整除,值得注意(y = a*b*c 即有a<y , b<y, c<y)

综上所述,我们判断x是否是素数时候,我们只需用2 . . sqrt(x)之间的素数去试除x 即可。

但是问题来了,如何求2 . . sqrt(x)之间的素数。

例如给定一个x = 23 判断它是否是素数。

方法一:
    用 2 和 2 . . sqrt(23)之间的奇数去试除,尝试次数是 2 次
方法二:
    用 2 . . sqrt(x)之间的素数去试除,首先得求出2 . . sqrt(2) 之间的素数2、3 次数为2、再用求出的素数去试除x、次数再加2 所以总次数是4, 很明显这样的效率更低了。

我们怎样提高方法二的效率呢?

呵呵。。。给我一张小于x 的素数表,我就可以直接省去了之前求2 . . sqrt(x) 之间的素数这个步骤了,是不!!  那么这样会不会快很多呢?

给定x = 107
用方法一我们所用试除次数是5次 分别要试除(2、3、5、7、9)

用方法二(假定我们是已经知道2 . . sqrt(x)之间素数的情况)所要试除的次数是4 ,分别要试除(2、3、5、7)

或许这样还不明显 再来,
给定x = 1999

用方法一所要试除次数是22次,分别要试除(2、3、5、7、9、、、23)
用方法二(假定我们是已经知道2 . . sqrt(x)之间素数的情况)所用次数是15次。

由此看出,随着x的不断增大,方法二的优势不断地扩大。

但问题是我们怎么保证我们每次判断x是否是素数时候,确保已经知道2 . . sqrt(x) 之间的素数。

最简单的方法是维护一张素数表,那么怎样快速得到一张素数表呢?
之前看过一篇文章叫筛法选素数:

1. 给定一个自然数序列2..N

2. 首先把能被2整除的所有数去掉,当然2除外

3. 类似的,把能被3整除的数去掉,同样3除外

4. 依次类推,一直到sqrt(N)

5. 筛选剩下的就是素数


快速得到素数表实现如下:

def prime():  
    NUM = 1000
    data = [2*i+1 for i in range(NUM)]
    data[0]=2
    for i in range(4,len(data)):
        j = 1
        while data[j] <= math.sqrt(data[i]):
            if data[j] != 0 and data[i]%data[j]==0:
                data[i] = 0
                continue       
            j += 1
    data = [x for x in data if x!=0]
    print data

这样就得到了2 . . 2*NUM+1 之间的素数,其实这也是利用了我们上面提到的方法二求素数,判断一个数是否是素数,则用2 .. sqrt(x)之间的素数去试除,这样效率是比单个单个去求省去不少时间。你说呢是不是?。。。。


好吧。。。废话扯了一大堆。。。。

只为了说明一个事实,

当你要判断一个数是否是 素数时,可以用2 和 2 . . sqrt(x)之间的奇数去试除,这样效率比较高

当你要连续判断若干(我指的若干是比较大的数量级)个数是否是素数时,你不妨先维护自己的一张素数表,在已知素数表的情况下帮你判断若干个数是否是素数时,效率可以大大提高。


以上纯属扯淡,各位看官,笑笑就好,不必当真。



原文链接:http://pkcb526546.iteye.com/blog/1991157

作者:zihua | 分类: python 学习 | 标签: python 素数 效率 | 阅读: 863 | 发布于: 2013-12-19 10时 |