SPOJ :: 2. Prime Generator

普段、C,C++しか書かないので、pythonも慣れていかないなーと思ったのでSPOJをpythonで解いていくことにした。

https://www.spoj.pl/problems/PRIME1/
問題概要：
整数[n,m]の範囲の素数を出力する。(1 <= m <= n <= 1000000000, n-m<=100000)
テストケースは最大で10個

エラトステネスの篩いだと、nが大きいから遅いというかpythonだとメモリ的に取れませんでした。
区間が最大でも100000と狭いので区間篩いで解く。

#!/usr/bin/python
# -*- coding: utf-8 -*-
import sys
import math

def 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 i

if __name__ == '__main__' :
    main()

区間篩いのコードは、蟻本のコードを移植しただけです。
このコードで 3.16sec
pythonの上位陣の速度と比較すると圧倒的に遅い。
テストケースの数も最大10個と少ないので、遅い遅いと言われてるpythonの入力関係の処理ではなさそう。
出力処理の可能性はあるけど、よくわかりません。
もっと高速なアルゴリズム使ってるのかな…。