首页 > 代码库 > SPOJ Python Day2： Prime Generator

SPOJ Python Day2： Prime Generator

2024-07-09 11:10:25   224人阅读

2. Prime Generator

任务很简单，生成m到n之间的所有质数。一个比较常见的思路是:

自然数$1, 2， …, N$中的最大的质因子要小于$\sqrt{N}$。所以用m到n中的每一个数去试除1到$\sqrt{n}$中的所有数。能整除就是合数，全不能整除就是质数。

但是这么做会超时。。

一般生成质数有一个常用的算法：筛法

http://zh.wikipedia.org/wiki/%E5%9F%83%E6%8B%89%E6%89%98%E6%96%AF%E7%89%B9%E5%B0%BC%E7%AD%9B%E6%B3%95 (wiki)的地址

这里边讲的非常好，也给出了伪代码。

主要是在自然数$[2, \sqrt{n}]$中生成一个逻辑序列，假设default都是True，从2开始把$i$的$i(i, (i+1), (i+2), …, (i+q)…)$全部变成False，然后从下一个TRUE开始循环。循环后可以得到所有$[2, \sqrt{n}]$的质数，然后用$[m, n]$里的数去除这些含这些质因子的倍数的数们。。

就是这样啦~

#!/usr/bin/python# -*- coding: utf-8 -*-import sysimport mathdef segment_sieve(a,b):    N = int(math.ceil(math.sqrt(b)))    is_prime_small = [True for x in range(N)]    is_prime = range(a,b)    for i in range(2,N):        if is_prime_small[i] :            for j in range(2*i,N,i):                is_prime_small[j] = False            for j in range(max(2,(a+i-1)/i)*i, b, i):                is_prime[j-a] = 1        return filter(lambda x:x>1, is_prime)def main():    T = int(sys.stdin.readline())    for t in range(T):        if t>0 :            print        n,m = [int(x) for x in sys.stdin.readline().split(‘ ‘)]        primes = segment_sieve(n,m+1)        for i in primes:            print iif __name__ == ‘__main__‘ :    main()


联系
我们