这是一个关于代码挑战的问题，请不要提供太多代码。我想尽可能自己解决这个问题。
我最近开始参加代码挑战，并将其与学习Python结合起来(我白天是前端javascript开发人员;))。到目前为止，一切都很顺利，我相信这是学习一门新语言的最好方法(至少对我来说)。
我目前遇到了一个挑战，要求我打印给定范围内的所有素数，这都是通过简单的Stdin和Stdout完成的。
到目前为止，我已经尝试了两种方法，都是工作，但太慢了。下面是一个链接和代码，我最快的实现到目前为止。也许我错过了一些非常明显的东西，导致我的python脚本变慢。目前，单个测试用例使用1.76s，范围为1, 100000
http://ideone.com/GT6Xxk(您也可以在这里调试脚本)
from sys import stdin
from math import sqrt, ceil
next(stdin) # skip unecessary line that describes the number of test cases
def is_prime(number):
initial_divider = sqrt(number)
if number == 2:
return True
elif number % 2 == 0 or int(initial_divider) == initial_divider:
return False
for divider in range(ceil(initial_divider), 1, -1):
if number % divider == 0:
return False
return True
for line in stdin:
low, high = [int(x) for x in line.split(' ')]
primes = [number for number
in range(max(low, 2), high+1)
if is_prime(number)]
for prime in primes:
print (prime)
print('')
"任务"/挑战的描述如下:
输入输入以单行中测试用例的数量t开始(t<=10)。在接下来的t行中，每一行有两个数字m和n (1 <= m<= n <=>1000000000, n-m<=100000)，中间用一个空格分隔。
输出对于每个测试用例打印所有素数p，使得m <= p <= n，每行一个数字>，测试用例用空行分隔。
更新1:我清理了最后一个块的逻辑，其中收集质数并打印完成:
for line in stdin:
low, high = [int(x) for x in line.split(' ')]
for number in range(max(low, 2), high+1):
if is_prime(number):
print (number)
print('')
1)它可能由控制台IO主导，打印输出。我更改了输出，因此它使用生成器收集素数，将数字转换为字符串，并用换行符将数字连接起来。这将在构建列表时节省一些内存，并将一些Python列表迭代推入Python运行时。在我的PC上进行的不科学的仓促测试中，这让它的速度提高了30%，但在ideone上却没有多大区别。(这可能是因为我把它移植到Python 2中运行，Python 2有一些非常不同的迭代/列表/生成器工作方式，但在ideone上使用了Python 3)。
2)每次都运行if number == 2: return True测试;在前10万个数字中，大多数不是2。在打印其余质数之前，我把它提取出来打印2。非常小的变化，不值得。
3)你的范围计数 - range(ceil(initial_divider), 1, -1) -这真的很奇怪。一个数被3整除的概率比被19整除的概率大得多。每第三个数能被3整除，只有第19个数能被19整除。为了快速返回函数，先试试小除法，对吧?我将它设置为向上计数。速度明显提高，希望还能用
这是原始运行时间的50%，在一个随意且完全不可比较的情况下。代码现在看起来像这样:
from sys import stdin
from math import sqrt, ceil
next(stdin) # skip unecessary line
def is_prime(number):
initial_divider = sqrt(number)
if number % 2 == 0 or int(initial_divider) == initial_divider:
return False
for divider in range(2, ceil(initial_divider)+1):
if number % divider == 0:
return False
return True
for line in stdin:
low, high = [int(x) for x in line.split(' ')]
primes = 'n'.join(str(number) for number
in range(max(low, 3), high+1)
if is_prime(number))
if low <= 2: print(2)
print (primes)
print('')
更改列表理解为生成器，脚本将运行得更快。
for number in range(max(low, 2), high+1):
if is_prime(number):
yield number
在像C或c++这样的语言中，SPOJ PRIME 1问题可以很容易地通过暴力破解来解决，即通过编写代码在不到一秒的时间内筛除1000,000,000以内的所有数字，从而保持在时间限制之内。甚至可能在Java、c#或Delphi中。但是如果在Python中是可能的，那么它可能是非常困难的，并且需要一些严肃的fu。
但是，请注意，SPOJ PRIME 1并没有要求筛选10亿个数字;它要求筛选几个不超过100001数字的小范围，并且它可能只查询少数范围。假设范围的数量是100(可能少得多)平均宽度是100000(可能少得多)那么仍然只有1000000个数字。在这种情况下，对全部十亿进行筛选需要做两个数量级的工作，这就是为什么SPOJ PRIME 1能够如此精确地剔除糠，尽管专家们使用了各种各样的语言。因此，诀窍是只做被要求做的事情——筛选作为输入提供的范围。即使是最简单、最直接的代码也可以用大量的时间来完成(c++:总共大约一毫秒)。这个原理和我对从一个上界为1000,000,000的范围内随机抽取100个素数的问题的回答完全一样，同样的解决方案也适用。关键是编写一个可以筛选给定范围(窗口)的函数，而不必筛选下面的所有数字。
此外，如何击败SPOJ PRIME 1的问题已经被问过很多次了，给出的答案仍然有效。小选择:
- 如何有效地筛选选定的质数范围?
- 获取两个大数之间质数的高效算法
- 生成m和n之间的素数
- spoj prime1: tle
- Erastothenes c++ SPOJ的分段筛
- 使用eratosthenes筛的Spoj PRIME1 (in C)
- …
def PrimesBelow(limit):
np=set()
p=[2]
for i in xrange(1,limit+1,2):
if i == 1: continue
if i in np: continue
beg=2 if i % 2 == 0 else 0
for j in xrange(beg,int(limit)+1,i):
np.add(j)
p.append(i)
return i
LetzerWille是正确的。上面的函数将返回(limit)以下的素数列表。我认为这个函数将比检查每个数字是否是素数运行得更快，因为这个函数将删除每个数字的乘法并将它们添加到(np)。旁注:这个函数只测试奇数。
简单的改进。看到这么简单的代码真让人尴尬。我的要长得多，慢得多:(…但是我学到了很多:)
还增加了测量时间的简单函数mt()
def PrimesBelow(limit):
np=set()
p=[2]
for i in range(3,limit+1,2):
if i in np: continue
beg = i*i
for j in range(beg,int(limit)+1,i):
np.add(j)
p.append(i)
return p
def mt(n):
import time
t = time.time()
pr = PrimesBelow(n)
print("#-Primes: {}, Time: {}".format(len(pr), round(time.time()-t, 4)))
return pr
pr = mt(100000000)
在16GB的i7-3770上大约是49秒
这将是执行次数较少的优化代码，它可以在一秒钟内计算和显示10000个素数。它利用了质数性质如果一个数不能被小于其平方根的数整除，则该数为素数。*我们可以在35次迭代内结束循环，而不是检查到最后(意味着1000次迭代来确定1000是否是素数)。* break如果在开始时被任何数字除，则循环(如果是偶数，则循环将在第一次迭代时中断，如果它可被3整除则迭代2次)，因此我们迭代直到结束，仅针对素数
记住一件事，你仍然可以通过使用属性*来优化迭代如果一个数字不能被小于它的素数整除那么它就是素数，但是代码会太大，我们必须跟踪计算的素数，而且很难找到一个特定的数字是否是素数，所以这将是最好的逻辑或代码
import math
number=1
count = 0
while(count<10000):
isprime=1
number+=1
for j in range(2,int(math.sqrt(number))+1):
if(number%j==0):
isprime=0
break
if(isprime==1):
print(number,end=" ")
count+=1
print("nCount "+str(count))