玩蛇网提供最新Python编程技术信息以及Python资源下载!

Python求两个数之间所有的素数求思路

题目要求:Prime Generator http://www.spoj.com/problems/PRIME1/

要求计算最多10组,每组由两个数m,n构成(1<=m<=n<=1000000000,n-m<100000),要求打印出m,n之间的所有素数(包括m,n),时间限制6s。下面是我采用筛法写的python代码,但是仍然超时,到底是哪里错了呢?

我写的代码:

from math import sqrt

def PrimeGenerator():
    n = input()
    a = range(n)

    for i in range(n):
        a[i] = raw_input().split()

    for aa in a:
        start = int(aa[0])
        end = int(aa[-1])
        length = end - start + 1
        l = [True] * length    
        for i in range(2, int(sqrt(end)) + 1):  # 筛子
            if start == 1:   # 排除1
                k = i * 2
                while k <= end:
                    l[k-start] = False
                    k += i
                l[0] = False
            elif start == 2: # 2是素数
                k = i * 2
                while k <= end:
                    l[k-start] = False
                    k += i
            else:  # 有一些下限值小于筛子的情况
                k = start <= i and i * 2 or i * (start / i)
                while k <= end:
                    if k >= start:
                        l[k-start] = False
                    k += i
        for i in range(length):
            if l[i]:
                print i + start
        print

PrimeGenerator()

筛法从时间复杂度上就没法满足题目的要求,超时是必然的。 筛法求出小于sqrt(1000000000)的所有素数(大约3400个),然后用这些素数再筛一次来判断[m, n]之间的数是否是素数。

或者试试 fermat test 或者 miller-rabin test 吧因为是概率算法,会WA。

http://www.zhihu.com/question/24236455/answer/27138389

终于过了,由于之前的筛子不是素数,所以比较慢。先把2-sqrt(1,000,000,000)之间的素数过滤出来,再去筛就很快了。修改之后的代码是这样的,代码结构可能不是很好,但是逻辑是对的。

from math import sqrt

def Primes(primes=[]):
    for i in range(3,31622,2):
        isprime = True
        cap = sqrt(i)+1
        for j in primes:
            if (j >= cap):
                break
            if (i % j == 0):
                isprime = False
                break
        if (isprime):
            primes.append(i)

def PrimeGenerator():
    primes = [2]
    Primes(primes)

    n = input()
    a = range(n)

    for i in range(n):
        a[i] = raw_input().split()

    for aa in a:
        start = int(aa[0])
        end = int(aa[-1])
        length = end - start + 1
        l = [True] * length
        for i in primes:
            if i > sqrt(end):
                break
            if start == 1:
                k = i * 2
                while k <= end:
                    l[k-start] = False
                    k += i
                l[0] = False
            elif start == 2:
                k = i * 2
                while k <= end:
                    l[k-start] = False
                    k += i
            else:
                k = start <= i and i * 2 or i * (start / i)
                while k <= end:
                    if k >= start:
                        l[k-start] = False
                    k += i
        for i in range(length):
            if l[i]:
                print i + start
        print

PrimeGenerator()

玩蛇网文章,转载请注明出处和文章网址:https://www.iplaypy.com/wenda/wd20049.html

相关文章 Recommend

玩蛇网Python互助QQ群,欢迎加入-->: 106381465 玩蛇网Python新手群
修订日期:2017年05月31日 - 10时53分38秒 发布自玩蛇网

您现在的位置: 玩蛇网首页 > Python问题解答 > 正文内容
我要分享到:

必知PYTHON教程 Must Know PYTHON Tutorials

必知PYTHON模块 Must Know PYTHON Modules