SPOJ 2. Prime Generator.py

題目連結：http://www.spoj.com/problems/PRIME1/ (opens new window) 給予 $m$ and $n$ $(1 \le m \le n \le 10^9, n-m \le 10^5)$，輸出這個範圍內的所有質數。

解題報告

果然不出所料，噴了一個 TLE 給我，囧。

# TLE
from sys import stdin
from math import sqrt

p = [2,3,5,7]

def is_prime(ia):
	if ia<2:
		return False
	for prime in p:
		if prime*prime > ia:
			break
		if ia % prime == 0:
			return False
	return True

def build_prime(prime_max):
	prime_max = int(sqrt(prime_max))
	i = 11
	j = 2
	while p[-1]<=prime_max:
		if is_prime(i):
			p.append(i)
		i+=j
		j=6-j

build_prime(10**9)
# print(len(p))
# print(p)

for t1 in range(int(stdin.readline())):
	inp = [int(i) for i in stdin.readline().split(' ')]
	if t1 != 0:
		print()
	for i in range(inp[0],inp[1]+1):
		if is_prime(i):
			print(i)

上網找了別人的程式碼 連結 (opens new window)，發現還可以利用 buffer 的方式加速，於是，開始動手修改：

# TLE
from sys import stdin
from math import sqrt

p = [2,3,5,7]
output=''

def is_prime(ia):
	if ia<2:
		return False
	for prime in p:
		if prime*prime > ia:
			break
		if ia % prime == 0:
			return False
	return True

def build_prime(prime_max):
	prime_max = int(sqrt(prime_max))
	i = 11
	j = 2
	while p[-1]<=prime_max:
		if is_prime(i):
			p.append(i)
		i+=j
		j=6-j

build_prime(10**9)
# print(len(p))
# print(p)

for t1 in range(int(stdin.readline())):
	m,n = [int(i) for i in stdin.readline().split(' ')]
	if t1 != 0:
		output+='\n'
	if m<=2<=n:
		output+='2\n'
	m += (m%2==0)
	n -= (n%2==0)
	for i in range(m,n+1,2):
		if is_prime(i):
			output+=str(i)+'\n'
print(output,end='')

結果仍然是 TLE，看來要繼續加速！根據 Colin Su 的建議，改成使用 array 來建表，並且預先配置記憶體，避免在執行期間不停的重新配置。

# TLE
from sys import stdin
from math import sqrt
from array import *

p = array('l',[0]*3402)
p[:4] = array('l',[2,3,5,7])
p_cnt = 4
output=''

def is_prime(ia):
	global p_cnt
	if ia<2:
		return False
	for i in range(p_cnt):
		if p[i]*p[i] > ia:
			break
		if ia % p[i] == 0:
			return False
	return True

def build_prime(prime_max):
	global p_cnt
	prime_max = int(sqrt(prime_max))
	i = 11
	j = 2
	while p[p_cnt-1]<=prime_max:
		if is_prime(i):
			p[p_cnt]=i
			p_cnt+=1
		i+=j
		j=6-j

build_prime(10**9)
# print(len(p))

for t1 in range(int(stdin.readline())):
	m,n = [int(i) for i in stdin.readline().split(' ')]
	if t1 != 0:
		output+='\n'
	if m<=2<=n:
		output+='2\n'
	m += (m%2==0)
	n -= (n%2==0)
	for i in range(m,n+1,2):
		if is_prime(i):
			output+=str(i)+'\n'
print(output,end='')

又一次的 TLE，看來這題真的無法偷懶，一定只能用篩法…老實說沒練過篩法的程式，所以寫了超久…好在終於 AC 啦

# AC
from sys import stdin
from math import sqrt
from array import *

p = array('l',[0]*3402)
p[:4] = array('l',[2,3,5,7])
p_cnt = 4
output=''

def is_prime(ia):
	global p_cnt
	if ia<2:
		return False
	for i in range(p_cnt):
		if p[i]*p[i] > ia:
			break
		if ia % p[i] == 0:
			return False
	return True

def build_prime(prime_max):
	global p_cnt
	prime_max = int(sqrt(prime_max))
	i = 11
	j = 2
	while p[p_cnt-1]<=prime_max:
		if is_prime(i):
			p[p_cnt]=i
			p_cnt+=1
		i+=j
		j=6-j

build_prime(10**9)
# print(len(p))

for t1 in range(int(stdin.readline())):
	m,n = [int(i) for i in stdin.readline().split(' ')]
	if t1:
		output += '\n'
	if m<2:
		m = 2
	sign = array('b',[1]*(n-m+1))
	for i in range(p_cnt):
		if p[i]*p[i]>n:
			break
		start = p[i]+p[i]-m
		if start<0:
			start %= p[i]
		sign[start::p[i]] = array('b',[0]*len(sign[start::p[i]]))
	for i in range(m,n+1):
		if sign[i-m]:
			output += str(i)+'\n'
print(output,end='')