打印给定范围内的所有质数，算法太慢..如何改进？ （代码挑战）
printing all prime numbers in given range, algorithm too slow.. how to improve? (code-challenge)
这是一个关于代码挑战的问题，请不要提供太多代码。我想尽可能自己解决这个问题。
我最近开始参加代码挑战，并将其与学习相结合 Python（我白天是前端 javascript 开发人员 ;)）。到目前为止一切顺利，我相信这是学习一门新语言的最佳方式（至少对我而言）。
我目前遇到了一个挑战，要求我打印给定范围内的所有质数，这一切都是通过简单的 Stdin 和 Stdout 完成的。
到目前为止我已经尝试了两种方法，两种方法都有效但速度太慢.. 下面是 link 和我目前最快实现的代码。也许我遗漏了一些非常明显的东西，导致我的 python 脚本变慢。目前，范围为 1, 100000
的单个测试用例需要 1.76s
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('')
'assignment'/挑战的描述如下：
Input
The input begins with the number t of test cases in a single line (t<=10). In >each of the next t lines there are two numbers m and n (1 <= m <= n <= >1000000000, n-m<=100000) separated by a space.
Output
For every test case print all prime numbers p such that m <= p <= n, one number >per line, test cases separated by an empty line.
更新 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('')
将列表理解更改为生成器，脚本将 运行 更快。
for number in range(max(low, 2), high+1):
if is_prime(number):
yield number
1) 可能是控制台IO为主，打印输出。我更改了输出，因此它使用生成器来收集素数，将数字转换为字符串，并用换行符连接数字。这应该在列表构建中节省一些内存，并将一些 Python 列表迭代推入 Python 运行 时间。这使得在我的 PC 上进行不科学的仓促测试时速度提高了约 30%，但在 ideone 上并没有太大区别。 （这可能是因为我在 Python 2 中将它设置为 运行，它有一些非常不同的 iteration/list/generator 工作原理，但在 ideone 上使用 Python 3）。
2) 你每次都运行 if number == 2: return True 测试；在前 100,000 个数字中，大多数不是 2。我在打印其余素数之前提取它以打印 2。非常小的改动，不值得。
3) 你的范围计数 down - range(ceil(initial_divider), 1, -1) - 这真的很奇怪。一个数字除以 3 的可能性比除以 19 的可能性要大得多。每隔 3 个数字除以 3，只有第 19 个数字除以 19。因此对于函数的 quick-return，请尝试使用 small首先是分隔线，对吧？我将它设置为计数 up。明显的速度提升，我希望它仍然有效。
这是原始 运行时间的 ~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('')
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 是对的。上面的函数将 return 下面的素数列表 (limit)。我认为这个函数 运行 比检查每个数字是否为素数更快，因为这个函数将删除每个数字的 乘法 并将它们添加到 (np)。
旁注：此函数将仅测试奇数。
在像 C 或 C++ 这样的语言中，SPOJ PRIME 1 问题可以很容易地通过蛮力解决，即通过编写代码在不到一秒的时间内筛选所有数字，直到 1000,000,000，从而保持低于时限。甚至可能在 Java、C# 或 Delphi 中。但是，如果在 Python 中完全有可能，那么它可能非常困难，需要一些严肃的 fu。
但是请注意，SPOJ PRIME 1 并不要求筛选十亿个数字；它要求筛选几个不超过 100001 个数字的小范围，并且它可能只查询少数几个范围。假设范围数是 100（可能少得多），平均宽度是 100000（可能少得多），那么仍然只有 10,000,000 个数字。在这种情况下筛选全部 10 亿项需要做两个数量级的工作，这就是为什么 SPOJ PRIME 1 能够如此精确地剔除谷壳，尽管专家们使用的语言范围很广。
因此诀窍是只做要求的事情——筛选作为输入提供的范围。即使是最简单、直接的代码也可以节省大量时间（C++：总共大约一毫秒）。原理和我对challenge of drawing 100 random primes from a range with an upper bound of 1,000,000,000的回答完全一样，同样的解决方法。关键是编写一个可以筛选给定范围 (window) 的函数，而不必筛选下面的所有数字。
此外，关于如何打败SPOJ PRIME 1的问题已经被问过无数次了，给出的答案仍然有效。一小部分：
- How do I efficiently sieve through a selected range for prime numbers?
- Efficient algorithm to get primes between two large numbers
- Generating prime numbers between m and n
- SPOJ PRIME1 : TLE
- Segmented Sieve of Erastothenes C++ SPOJ
- Spoj PRIME1 using sieve of eratosthenes (in C)
- ...
简单的改进。看到这个简单的代码很尴尬。我的又长又慢 :( ... 但我学到了很多 :)
同时添加用于测量时间的简单函数 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))
这是一个关于代码挑战的问题，请不要提供太多代码。我想尽可能自己解决这个问题。
我最近开始参加代码挑战，并将其与学习相结合 Python（我白天是前端 javascript 开发人员 ;)）。到目前为止一切顺利，我相信这是学习一门新语言的最佳方式（至少对我而言）。
我目前遇到了一个挑战，要求我打印给定范围内的所有质数，这一切都是通过简单的 Stdin 和 Stdout 完成的。
到目前为止我已经尝试了两种方法，两种方法都有效但速度太慢.. 下面是 link 和我目前最快实现的代码。也许我遗漏了一些非常明显的东西，导致我的 python 脚本变慢。目前，范围为 1, 100000
1.76s
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('')
'assignment'/挑战的描述如下：
Input
The input begins with the number t of test cases in a single line (t<=10). In >each of the next t lines there are two numbers m and n (1 <= m <= n <= >1000000000, n-m<=100000) separated by a space.
Output
For every test case print all prime numbers p such that m <= p <= n, one number >per line, test cases separated by an empty line.
更新 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('')
将列表理解更改为生成器，脚本将 运行 更快。
for number in range(max(low, 2), high+1):
if is_prime(number):
yield number
1) 可能是控制台IO为主，打印输出。我更改了输出，因此它使用生成器来收集素数，将数字转换为字符串，并用换行符连接数字。这应该在列表构建中节省一些内存，并将一些 Python 列表迭代推入 Python 运行 时间。这使得在我的 PC 上进行不科学的仓促测试时速度提高了约 30%，但在 ideone 上并没有太大区别。 （这可能是因为我在 Python 2 中将它设置为 运行，它有一些非常不同的 iteration/list/generator 工作原理，但在 ideone 上使用 Python 3）。
2) 你每次都运行 if number == 2: return True 测试；在前 100,000 个数字中，大多数不是 2。我在打印其余素数之前提取它以打印 2。非常小的改动，不值得。
3) 你的范围计数 down - range(ceil(initial_divider), 1, -1) - 这真的很奇怪。一个数字除以 3 的可能性比除以 19 的可能性要大得多。每隔 3 个数字除以 3，只有第 19 个数字除以 19。因此对于函数的 quick-return，请尝试使用 small首先是分隔线，对吧？我将它设置为计数 up。明显的速度提升，我希望它仍然有效。
这是原始 运行时间的 ~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('')
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 是对的。上面的函数将 return 下面的素数列表 (limit)。我认为这个函数 运行 比检查每个数字是否为素数更快，因为这个函数将删除每个数字的 乘法 并将它们添加到 (np)。 旁注：此函数将仅测试奇数。
在像 C 或 C++ 这样的语言中，SPOJ PRIME 1 问题可以很容易地通过蛮力解决，即通过编写代码在不到一秒的时间内筛选所有数字，直到 1000,000,000，从而保持低于时限。甚至可能在 Java、C# 或 Delphi 中。但是，如果在 Python 中完全有可能，那么它可能非常困难，需要一些严肃的 fu。
但是请注意，SPOJ PRIME 1 并不要求筛选十亿个数字；它要求筛选几个不超过 100001 个数字的小范围，并且它可能只查询少数几个范围。假设范围数是 100（可能少得多），平均宽度是 100000（可能少得多），那么仍然只有 10,000,000 个数字。在这种情况下筛选全部 10 亿项需要做两个数量级的工作，这就是为什么 SPOJ PRIME 1 能够如此精确地剔除谷壳，尽管专家们使用的语言范围很广。
因此诀窍是只做要求的事情——筛选作为输入提供的范围。即使是最简单、直接的代码也可以节省大量时间（C++：总共大约一毫秒）。原理和我对challenge of drawing 100 random primes from a range with an upper bound of 1,000,000,000的回答完全一样，同样的解决方法。关键是编写一个可以筛选给定范围 (window) 的函数，而不必筛选下面的所有数字。
此外，关于如何打败SPOJ PRIME 1的问题已经被问过无数次了，给出的答案仍然有效。一小部分：
- How do I efficiently sieve through a selected range for prime numbers?
- Efficient algorithm to get primes between two large numbers
- Generating prime numbers between m and n
- SPOJ PRIME1 : TLE
- Segmented Sieve of Erastothenes C++ SPOJ
- Spoj PRIME1 using sieve of eratosthenes (in C)
- ...
简单的改进。看到这个简单的代码很尴尬。我的又长又慢 :( ... 但我学到了很多 :)
同时添加用于测量时间的简单函数 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))