Python编程:筛法求两个数之间的素数
ringa_lee
ringa_lee 2017-04-17 11:42:40
0
3
563

题目要求: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()
ringa_lee
ringa_lee

ringa_lee

reply all (3)
伊谢尔伦

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

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

    伊谢尔伦

    终于过了,由于之前的筛子不是素数,所以比较慢。先把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()
      左手右手慢动作

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

        Latest Downloads
        More>
        Web Effects
        Website Source Code
        Website Materials
        Front End Template
        About us Disclaimer Sitemap
        php.cn:Public welfare online PHP training,Help PHP learners grow quickly!