一些基本且低效的素数生成算法
(重定向自一个更有效的素数生成算法)
 |
一位维基教科书用户认为此页面应该拆分为更小的页面，内容更集中。 你可以通过将这个大页面拆分成更小的页面来帮助。请确保遵循命名策略。将书籍分成更小的部分可以提供更多焦点，并允许每个部分都能做好一件事，这对每个人都有益。 |
在任何典型的编程语言课程中，学生都会得到一个项目，编写一个生成素数的程序。这被认为是一个相对简单的任务，在课程的前几周内就会被分配。我相信你已经知道，一些简单有效的算法可以用在不到几分钟的时间内完成这个任务。在以下示例中，我将使用 Python2.5 编程语言来演示这些算法并比较它们的效率。
我们将考虑的第一个算法将从整数 2 开始，然后选择每个连续的整数作为潜在的素数 (pp)，通过测试它是否可以被任何先前识别的素数分解来检查素数性，然后将每个新验证的素数存储在一个素数集 (ps) 数组中。
pp = 2
ps = [pp]
lim = raw_input("\nGenerate prime numbers up to what number? : ")
while pp < int(lim):
pp += 1
for a in ps:
if pp % a == 0:
break
else:
if pp not in ps:
ps.append(pp)
print ps
注意：上面给出的代码不构成一个完整的程序。参见附录 A，其中包含一个包含用户界面的完整程序。
这样一个基本的算法采用严格的蛮力方法，有效地实现了识别每个素数并将其存储在一个数组中的目标。我相信你会同意，这也是生成素数最不有效的方式。正如我们将在下文中看到的，使用筛分过程的元素将提高我们程序的效率，同时避免真正的埃拉托斯特尼筛法的耗时特性，它在识别每个连续整数作为潜在素数之前将其作为可分解的整数进行识别，并将其作为素数排除，就像 PGsimple1 所做的那样。
运行时数据
primes pgsimple1
up to takes
100 .00100 sec
1000 .02800 sec
10000 1.6980 sec
100000 130.44 sec
1000000 10732 sec
|
这些是在每次限制下 5 次测试运行中取得的最佳时间结果。
此表记录了 pgsimple1 在每个指示的限制下的运行时间。请接受这些运行时间以及本文档中给出的所有运行时间可能与你在拥有不同硬件或软件的计算机上运行相同程序时获得的运行时间略有不同，我的计算机拥有 AMD Turion 64 1.9 GHz，内存为 2 GB，硬盘为 160 GB，操作系统为 Windows Vista。
改进此算法的第一步可能是有效地选择潜在素数。在算法中，最常见的是看到这样的设备，它从整数 3 开始，然后仅通过选择连续的奇数整数作为潜在素数来进行。这样减少了必须测试的潜在素数总数的一半。
pp = 2
ps = [pp]
pp += 1
ps.append(pp)
lim = raw_input("\nGenerate prime numbers up to what number? : ")
while pp < int(lim):
pp += 2
test = True
for a in ps:
if pp % a == 0:
test = False
break
if test:
ps.append(pp)
return ps
现在，蛮力方法通过一些简单的逻辑得到了增强，从而显着提高了效率，将潜在素数的数量减少了一半。
运行时数据
primes pgsimple2 times faster compared
up to takes to pgsimple1
100 0.0 ~
1000 .01400 2.00
10000 .85700 1.98
100000 65.240 2.00
1000000 5392.9 1.99
10000000 458123 ~
|
这些是在每次限制下 5 次测试运行中取得的最佳时间结果。
此表记录了 pgsimple2 的运行时间，以及它在每个限制下完成运行的速度是 pgsimple1 的多少倍。请注意，效率在任何限制下都保持接近 pgsimple1 的两倍。即使以这种速度，生成 8 位素数或更多位素数仍然是不切实际的。但是，我只是为了看看需要多长时间才做到了这一点。
下一个最明显的改进可能是将测试过程限制在只检查潜在素数是否可以被小于或等于该潜在素数平方根的素数分解，因为大于该潜在素数平方根的素数将是小于该潜在素数平方根的至少一个素数的互补因子。
from math import sqrt
pp = 2
ps = [pp]
pp += 1
ps.append(pp)
lim = raw_input("\nGenerate prime numbers up to what number? : ")
while pp < int(lim):
pp += 2
test = True
sqrtpp = sqrt(pp)
for a in ps:
if a > sqrtpp:
break
if pp % a == 0:
test = False
break
if test:
ps.append(pp)
return ps
这个算法在效率上取得了真正重大的进步，并且在这个阶段，大多数程序员已经用尽了他们继续提高素数生成器效率的能力或愿望，但我们将继续前进。
运行时数据
primes pgsimple3 times faster compared times faster compared
up to takes to pgsimple1 to pgsimple2
100 0.0 ~ ~
1000 .00300 9.33 4.67
10000 .06200 27.4 13.8
100000 1.1220 116 58.1
1000000 26.979 398 200
10000000 705.37 ~ 649
100000000 18780 ~ ~
|
这些是在每次限制下 5 次测试运行中取得的最佳时间结果。
此表记录了 pgsimple3 的运行时间，以及它在每个限制下完成运行的速度是 pgsimple1 和 pgsimple2 的多少倍。请注意，程序运行的时间越长，效率就越显著。
认识到通过使用 2 的跳数来选择仅奇数潜在素数，不再需要根据小于该素数平方根的所有素数来测试潜在素数，因为它们都不能被 2 分解。因此，我们可以从我们测试潜在素数的素数集中删除第一个素数。这需要将素数集 (ps) 数组分成排除素数 (ep) 和测试素数 (tp) 数组，然后在最后将它们重新组合，以便将完整的集合发送回函数调用。
from math import sqrt
pp = 2
ep = [pp]
pp += 1
tp = [pp]
ss = [2]
lim = raw_input("\nGenerate prime numbers up to what number? : ")
while pp < int(lim):
pp += ss[0]
test = True
sqrtpp = sqrt(pp)
for a in tp:
if a > sqrtpp:
break
if pp % a == 0:
test=False
break
if test:
tp.append(pp)
ep.reverse()
[tp.insert(0,a) for a in ep]
return tp
在下一个版本中，将显示为什么我们将跳数 (2) 放入一个跳数集 (ss) 数组中。
运行时数据
primes pgsimple4 times faster compared
up to takes to pgsimple3
100 0.0 ~
1000 .00300 1.00
10000 .05200 1.19
100000 1.1140 1.01
1000000 26.734 1.01
10000000 702.54 1.00
100000000 18766 1.00
|
这些是在每次限制下 5 次测试运行中取得的最佳时间结果。
此表记录了 pgsimple4 的运行时间，以及它在每个限制下完成运行的速度是 pgsimple3 的多少倍。
效率有什么提高？请注意，与 pgsimple3 相比，效率的提高只是微乎其微的。不用担心，随着我在接下来的版本中向你展示的更高级版本的程序中从测试过程中删除的素数越来越多，效率的提高会成倍增加。
该算法通过从考虑范围内排除先前识别的素数的倍数来有效地选择潜在素数，并最大程度地减少了验证每个潜在素数的素数性必须执行的测试次数。虽然选择潜在素数的效率允许程序在程序运行的时间越长，每秒筛选更多范围的数字，但需要对每个潜在素数执行的测试数量确实会继续增加（但与其他算法相比，增加的速度较慢）。总而言之，这些过程使生成素数变得更高效，使得在个人电脑上，即使在合理的时间内生成 10 位已验证的素数也成为可能。
可以开发进一步的跳数集，以排除可以被每个已经识别的素数分解的潜在素数的选择。尽管这个过程更加复杂，但它可以被概括并变得相当优雅。同时，我们可以继续从测试素数集中删除跳数集排除其倍数的每个素数，最大程度地减少对每个潜在素数必须执行的测试次数。这个示例中包含对每一行的全面注释和一些解释，以帮助读者充分理解算法的工作原理。一个包含用户界面但没有注释的完整程序可以在附录 B 中找到。
请忽略用户界面中出现的语法错误，例如“第 1 个素数”而不是“第 1 个素数”，以及在已完成的数组中包含最后生成的素数，即使它可能大于用户定义的限制。这些错误可以方便地由学生程序员进行更正，但对于说明算法的性能来说并不必要。对于由此可能给读者带来的任何困惑或不便，我表示歉意。
from math import sqrt
lim = raw_input("\nGenerate prime numbers up to what number? : ")
""" Get an upper limit from the user to determine the generator's termination point. """
sqrtlim = sqrt(float(lim))
""" Get the square root of the upper limit. This will be the upper limit of the test prime array
for primes used to verify the primacy of any potential primes up to (lim). Primes greater than
(sqrtlim) will be placed in an array for extended primes, (xp), not needed for the verification
test. The use of an extended primes array is technically unnecessary, but helps to clarify that we
have minimized the size of the test prime array. """
pp = 2
""" Initialize the variable for the potential prime, setting it to begin with the first prime
number, (2). """
ss = [pp]
""" Initialize the array for the skip set, setting it at a single member, being (pp=2). Although
the value of the quantity of members in the skip set is never needed in the program, it may be
useful to understand that future skip sets will contain more than one member, the quantity of which
can be calculated, and is the quantity of members of the previous skip set multiplied by one less
than the value of the prime which the new skip set will exclude multiples of. Example - the skip
set which eliminates multiples of primes up through 3 will have (3-1)*1=2 members, since the
previous skip set had 1 member. The skip set which eliminates multiples of primes up through 5 will
have (5-1)*2=8 members, since the previous skip set had 2 members, etc. """
ep = [pp]
""" Initialize the array for primes which the skip set eliminate multiples of, setting the first
member as (pp=2) since the first skip set will eliminate multiples of 2 as potential primes. """
pp += 1
""" Advance to the first potential prime, which is 3. """
rss = [ss[0]]
""" Initialize an array for the ranges of each skip set, setting the first member to be the range
of the first skip set, which is (ss[0]=2). Future skip sets will have ranges which can be
calculated, and are the sum of the members of the skip set. Another method of calculating the range
will also be shown below. """
tp = [pp]
""" Initialize an array for primes which are needed to verify potential primes against, setting the
first member as (pp=3), since we do not yet have a skip set that excludes multiples of 3. Also note
that 3 is a verified prime, without testing, since there are no primes less than the square root of
3. """
i = 0
""" Initialize a variable for keeping track of which skip set range is current. """
rss.append(rss[i] * tp[0])
""" Add a member to the array of skip set ranges, the value being the value of the previous skip
set range, (rss[0]=2), multiplied by the value of the largest prime which the new skip set will
exclude multiples of, (tp[0]=3), so 2*3=6. This value is needed to define when to begin
constructing the next skip set. """
xp = []
""" Initialize an array for extended primes which are larger than the square root of the user
defined limit (lim) and not needed to verify potential primes against, leaving it empty for now.
Again, the use of an extended primes array is technically unnecessary, but helps to clarify that we
have minimized the size of the test prime array. """
pp += ss[0]
""" Advance to the next potential prime, which is the previous potential prime, (pp=3), plus the
value of the next member of the skip set, which has only one member at this time and whose value is
(ss[0]=2), so 3+2=5. """
npp = pp
""" Initialize a variable for the next potential prime, setting its value as (pp=5). """
tp.append(npp)
""" Add a member to the array of test primes, the member being the most recently identified prime,
(npp=5). Note that 5 is a verified prime without testing, since there are no TEST primes less than
the square root of 5. """
while npp < int(lim):
""" Loop until the user defined upper limit is reached. """
i += 1
""" Increment the skip set range identifier. """
while npp < rss[i] + 1:
""" Loop until the next skip set range is surpassed, since data through that range is
needed before constructing the next skip set. """
for n in ss:
""" Loop through the current skip set array, assigning the variable (n) the value
of the next member of the skip set. """
npp = pp + n
""" Assign the next potential prime the value of the potential prime plus
the value of the current member of the skip set. """
if npp > int(lim):
break
""" If the next potential prime is greater than the user defined limit,
then end the 'for n' loop. """
if npp <= rss[i] + 1:
pp = npp
""" If the next potential prime is still within the range of the next skip
set, then assign the potential prime variable the value of the next
potential prime. Otherwise, the potential prime variable is not changed
and the current value remains the starting point for constructing the next
skip set. """
sqrtnpp = sqrt(npp)
""" Get the square root of the next potential prime, which will be the
limit for the verification process. """
test = True
""" Set the verification flag to True. """
for q in tp:
""" Loop through the array of the primes necessary for verification of the
next potential prime. """
if sqrtnpp < q:
break
""" If the test prime is greater than the square root of the next
potential prime, then end testing through the 'for q' loop. """
elif npp % q == 0:
""" If the test prime IS a factor of the next potential prime. """
test = False
""" Then set the verification flag to False since the next
potential prime is not a prime number. """
break
""" And end testing through the 'for q' loop. """
""" Otherwise, continue testing through the 'for q' loop. """
if test:
""" If the next potential prime has been verified as a prime number. """
if npp <= sqrtlim:
tp.append(npp)
""" And if the next potential prime is less than or equal to the
square root of the user defined limit, then add it to the array of
primes which potential primes must be tested against. """
else:
xp.append(npp)
""" Otherwise, add it to the array of primes not needed to verify
potential primes against. """
""" Then continue through the 'for n' loop. """
if npp > int(lim):
break
""" If the next potential prime is greater than the user defined limit, then end
the 'while npp<rss[i]+1' loop. """
""" Otherwise, continue the 'while npp<rss[i]+1' loop. """
if npp > int(lim):
break
""" If the next potential prime is greater than the user defined limit, then end the 'while
npp<int(lim)' loop. """
""" At this point, the range of the next skip set has been reached, so we may begin
constructing a new skip set which will exclude multiples of primes up through the value of
the first member of the test prime set, (tp[0]), from being selected as potential
primes. """
lrpp = pp
""" Initialize a variable for the last relevant potential prime and set its value to the
value of the potential prime. """
nss = []
""" Initialize an array for the next skip set, leaving it empty for now. """
while pp < (rss[i] + 1) * 2-1:
""" Loop until the construction of the new skip set has gone through the range of the new
skip set. """
for n in ss:
""" Loop through the current skip set array. """
npp = pp + n
""" Assign the next potential prime the value of the potential prime plus
the value of the current member of the skip set. """
if npp > int(lim):
break
""" If the next potential prime is greater than the user defined limit,
then end the 'for n' loop. """
sqrtnpp = sqrt(npp)
""" Get the square root of the next potential prime, which will be the
limit for the verification process. """
test = True
""" Set the verification flag to True. """
for q in tp:
""" Loop through the array of the primes necessary for verification of the
next potential prime. """
if sqrtnpp < q:
break
""" If the test prime is greater than the square root of the next
potential prime, then end testing through the 'for q' loop. """
elif npp % q == 0:
""" If the test prime IS a factor of the next potential prime. """
test = False
""" Then set the verification flag to False since the next
potential prime is not a prime number. """
break
""" And end testing through the 'for q' loop. """
""" Otherwise, continue testing through the 'for q' loop. """
if test:
""" If the next potential prime has been verified as a prime number. """
if npp <= sqrtlim:
tp.append(npp)
""" And if the next potential prime is less than or equal to the
square root of the user defined limit, then add it to the array of
primes which potential primes must be tested against. """
else:
xp.append(npp)
""" Otherwise, add it to the array of primes not needed to verify
potential primes against. """
if npp % tp[0] != 0:
""" If the next potential prime was NOT factorable by the first member of
the test array, then it is relevant to the construction of the new skip set
and a member must be included in the new skip set for a potential prime to
be selected. Note that this is the case regardless of whether the next
potential prime was verified as a prime, or not. """
nss.append(npp-lrpp)
""" Add a member to the next skip set, the value of which is the
difference between the last relevant potential prime and the next
potential prime. """
lrpp = npp
""" Assign the variable for the last relevant potential prime the
value of the next potential prime. """
pp = npp
""" Assign the variable for the potential prime the value of the next
potential prime. """
""" Then continue through the 'for n' loop. """
if npp > int(lim):
break
""" If the next potential prime is greater than the user defined limit, then end
the 'while npp<(rss[i]+1)*2-1' loop. """
""" Otherwise, continue the 'while npp<(rss[i]+1)*2-1' loop. """
if npp > int(lim):
break
""" If the next potential prime is greater than the user defined limit, then end the 'while
npp<int(lim)' loop. """
ss=nss
""" Assign the skip set array the value of the new skip set array. """
ep.append(tp[0])
""" Add a new member to the excluded primes array, since the newly constructed skip set
will exclude all multiples of primes through the first member of the test prime array. """
del tp[0]
""" Delete the first member from the test prime array since future potential primes will
not have to be tested against this prime. """
rss.append(rss[i] * tp[0])
""" Add a member to the skip set range array with the value of the range of the next skip
set. """
npp = lrpp
""" Assign the next potential prime the value of the last relevant potential prime. """
""" Then continue through the 'while npp<int(lim)' loop. """
""" At this point the user defined upper limit has been reached and the generator has completed
finding all of the prime numbers up to the user defined limit. """
ep.reverse()
""" Flip the array of excluded primes. """
[tp.insert(0, a) for a in ep]
""" Add each member of the flipped array into the beginning of the test primes array. """
tp.reverse()
""" Flip the array of test primes. """
[xp.insert(0, a) for a in tp]
""" Add each member of the flipped array into the beginning of the extended primes array. """
return xp
""" Send the completed array of all primes up to the user defined limit back to the function call. """
运行时数据
primes pg7.8 times faster compared times faster compared
up to takes to pgsimple1 to pgsimple4
100 0.0 ~ ~
1000 .00100 28.0 3.00
10000 .01800 94.3 2.89
100000 .28400 459 3.92
1000000 5.6220 1909 4.76
10000000 120.53 ~ 5.83
100000000 2752.1 ~ 6.82
1000000000 65786 ~ ~
|
这些是在每次限制下 5 次测试运行中取得的最佳时间结果。
此表记录了 pg7.8 的运行时间，以及它在每个限制下完成运行的速度是 pgsimple1 和 pgsimple4 的多少倍。请注意，程序运行的时间越长，效率就越显著。
感谢您抽出时间研究该算法，希望它能激发您的灵感。如果您选择将该算法翻译成其他编程语言，请将您的作品的副本发送电子邮件至 [email protected]。
好吧，所有步骤都ok，但你可以在一开始就停下来；只要你能说明所有 2N（其中 N>1）**都不是**素数，你也可以说除了 3 之外的所有素数都不在 3N 的形式中，等等。
这在第一步就导致了已知的素数形式 6N±1（这很优雅但错误，真正的形式是 6N+1 或 6N+5），但你可以做得更好，只要使用 30N+1、30N+7、30N+11 ...... 30N+29，或者甚至使用 210N+1、210N+11、210N+13 ...... 210N+209。
简而言之，使用一种算法以智能的方式缩减“搜索范围”，使用 1*1、1*2、1*2*3、1*2*3*5、1*2*3*5*7 .... 作为“基数”和一组“位移”进行添加。
但请注意，速度仍然受到多个、不断增长的“sqrt”和“div”（或更好的“mod”）操作的影响。
“sqrt”操作可以“反转”，只需执行 N^2 即可限制测试的有效性：在时间方面，这种方法非常有效！
同样，“模”操作也可以避免，但技巧有点长，以后再说。
因此，只要你能猜出素数并能够区分“真”素数和“假”素数，就无需计算素数。
如果你研究了算法，你会意识到它确实以一种智能的方式通过生成跳跃集来缩减“搜索范围”，这些跳跃集使用已知的素数作为基数，以 6N、30N、210N 等的形式进行过滤，并且随着每次生成，这种过滤会无限次进行，正如你所建议的那样。即使这样，只有大于跳跃集的基数素数的因子的数字，仍然需要通过与大于过滤素数但小于待测数字的平方根的素数进行测试来过滤。因此，必须至少生成所有小于待测最大数字平方根的素数。也就是说，区分“真”素数和“假”素数的唯一方法。
#! /usr/bin/env python
from math import sqrt
from time import time
def pg():
# pgsimple1, the least efficient algorithm
lim = raw_input("\nGenerate prime numbers up to what number? : ")
pp = 2
ps = [pp]
bt = time()
while pp<int(lim):
pp += 1
test = True
for a in ps:
if pp % a == 0:
test = False
if test:
ps.append(pp)
et = time()
tt = et - bt
a = test = et = bt = pp = 0
print "\nIt took",tt,"seconds to generate the prime set up to: ", lim, "\nwith", len(ps), "members."
tt = lim = 0
return ps
def ui(a):
m = "\nDo you wish to review the numbers? Enter y for yes or q to quit. "
n = "From: "
o = "To: "
p = "or"
q = "is out of the range of the set generated."
r = "and"
s = "There are none between"
t = "\nPlease pick between 0"
u = "\nThey are the"
v = "th thru"
w = "th members."
x = "\nPlease choose a number that is less than"
y = "a prime number."
z = "\nThere are"
A = "members of the prime set"
C = "Make a selection or enter q to quit. "
f = raw_input(m)
while f != 'q':
if f == 'y':
print "\nChoose a category:"
print "a) Pick a range of indexes of members of the prime number set."
print "b) Pick a range of numbers to view prime numbers in that range."
print "d) Input a number to check its membership in the prime number set."
print "e) Get the number of members in the prime set up to a particular number."
print "f) Get the number of members in the prime set between a range of numbers."
print "v) View 100 primes at a time."
f = raw_input(C)
if f == 'a':
print t, r, len(a)
f = raw_input(n)
g = raw_input(o)
if int(g) < int(f):
h = f
f = g
g = h
if int(f) < 0 or int(g) > len(a):
print f, p, g, q
elif f == g:
print s, f, r, g
else:
print [a[h] for h in range(int(f), int(g))], "\n", u, str(int(f) + 1) + v, str(g) + w
if f == 'b':
print t, r, a[len(a) - 1] + 1
f = raw_input(n)
g = raw_input(o)
if int(g) < int(f):
h = f
f = g
g = h
if int(f) < 0 or int(g) > a[len(a) - 1] + 1:
print f, p, g, q
elif f == g:
print s, f, r, g
else:
i = 0
while a[i] < int(f):
i += 1
j = i
while i < len(a) and a[i] <= int(g):
print a[i],
i += 1
print u, str(int(j) + 1) +v,str(i) + w
if f == 'd':
print x, a[len(a) - 1] + 1
f = raw_input("What number do you want to check? ")
for g in a:
if int(g) == int(f):
print f, "is", y
if int(g) > int(f):
print f, "is not", y
if int(f) < 0 or int(g) >= int(f):
break
if int(f) > g + 1 or int(f) < 0:
print f, q
if f == 'e':
print x, a[len(a) - 1] + 2
f = raw_input(o)
if -1 < int(f) <a[len(a) - 1] + 2:
g = 0
while a[g] <= int(f):
g += 1
if g == len(a):
break
print z, g, A, "up to", f
else:
print f, q
if f == 'f':
print t, r, a[len(a) - 1] + 1
f = raw_input(n)
g = raw_input(o)
if int(g) < int(f):
h = f
f = g
g = h
i = 0
if int(f) < 0 or int(g) > a[len(a) - 1] + 1:
print f, p, g, q
elif f == g:
print s, f, r, g
else:
for j in a:
if int(f) <= int(j) <= int(g):
i += 1
elif int(j) > int(g):
break
print z, i, A, "from", f, "thru", g
if f == 'v':
g = 0
h = 1
while f != 'q' and g < len(a):
i = h * 100
for g in range(100*(h - 1),i):
if g == len(a):
i = len(a)
break
print a[g],
print u, str(100 * (h - 1) + 1) + v, str(i) + w
h += 1
if g == len(a):
break
f = raw_input("\nView the next 100 members or enter q to quit. ")
f = raw_input(m)
def run(a = 'r'):
while a is 'r':
a = raw_input("\nEnter r to run prime generator. ")
if a != 'r':
b = pg()
ui(b)
if __name__ == "__main__":
run()
print "\n" * 5, "Don't go away mad...Just go away.", "\n" * 5
#! /usr/bin/env python
from math import sqrt
from time import time
def pg():
lim = raw_input("\nGenerate prime numbers up to what number? : ")
sqrtlim = sqrt(float(lim))
pp = 2
ep = [pp]
ss = [pp]
pp += 1
i = 0
rss = [ss[0]]
tp = [pp]
xp = []
pp += ss[0]
npp = pp
tp.append(npp)
rss.append(rss[i] * tp[0])
bt = time()
while npp < int(lim):
i += 1
while npp < rss[i] + 1:
for n in ss:
npp = pp + n
if npp > int(lim):
break
if npp <= rss[i] + 1:
pp = npp
sqrtnpp = sqrt(npp)
test = True
for q in tp:
if sqrtnpp < q:
break
elif npp % q == 0:
test = False
break
if test:
if npp <= sqrtlim:
tp.append(npp)
else:
xp.append(npp)
if npp > int(lim):
break
if npp > int(lim):
break
lrpp = pp
nss = []
while pp < (rss[i] + 1) * 2 - 1:
for n in ss:
npp = pp + n
if npp > int(lim):
break
sqrtnpp = sqrt(npp)
test = True
for q in tp:
if sqrtnpp < q:
break
elif npp % q == 0:
test = False
break
if test:
if npp <= sqrtlim:
tp.append(npp)
else:
xp.append(npp)
if npp % tp[0] != 0:
nss.append(npp - lrpp)
lrpp = npp
pp = npp
if npp > int(lim):
break
if npp > int(lim):
break
ss = nss
ep.append(tp[0])
del tp[0]
rss.append(rss[i] * tp[0])
npp = lrpp
et = time()
i = nss = npp = n = sqrtnpp = test = q = r = lrpp = rss = ss = pp = sqrtlim = 0
tt = et - bt
ep.reverse()
[tp.insert(0, a) for a in ep]
tp.reverse()
[xp.insert(0, a) for a in tp]
print "\nIt took", tt, "seconds to generate the prime set up to: ", lim, "\nwith", len(xp), "members."
et = bt = ep = tp = a = tt = lim = 0
return xp
def ui(a):
m = "\nDo you wish to review the numbers? Enter y for yes or q to quit. "
n = "From: "
o = "To: "
p = "or"
q = "is out of the range of the set generated."
r = "and"
s = "There are none between"
t = "\nPlease pick between 0"
u = "\nThey are the"
v = "th thru"
w = "th members."
x = "\nPlease choose a number that is less than"
y = "a prime number."
z = "\nThere are"
A = "members of the prime set"
C = "Make a selection or enter q to quit. "
f = raw_input(m)
while f != 'q':
if f == 'y':
print "\nChoose a category:"
print "a) Pick a range of indexes of members of the prime number set."
print "b) Pick a range of numbers to view prime numbers in that range."
print "d) Input a number to check its membership in the prime number set."
print "e) Get the number of members in the prime set up to a particular number."
print "f) Get the number of members in the prime set between a range of numbers."
print "v) View 100 primes at a time."
f = raw_input(C)
if f== 'a':
print t, r, len(a)
f = raw_input(n)
g = raw_input(o)
if int(g) < int(f):
h = f
f = g
g = h
if int(f) < 0 or int(g) > len(a):
print f, p, g, q
elif f==g: print s,f,r,g
else:
print [a[h] for h in range(int(f), int(g))], "\n" , u, str(int(f) + 1) + v, str(g) + w
if f == 'b':
print t, r, a[len(a) - 1] + 1
f = raw_input(n)
g = raw_input(o)
if int(g) < int(f):
h = f
f = g
g = h
if int(f) < 0 or int(g) > a[len(a) - 1] + 1:
print f, p, g, q
elif f == g:
print s, f, r, g
else:
i = 0
while a[i] < int(f):
i += 1
j = i
while i < len(a) and a[i] <= int(g):
print a[i],
i += 1
print u, str(int(j) + 1) + v, str(i) + w
if f == 'd':
print x, a[len(a) - 1] + 1
f = raw_input("What number do you want to check? ")
for g in a:
if int(g) == int(f):
print f, "is", y
if int(g) > int(f):
print f, "is not", y
if int(f) < 0 or int(g) >= int(f):
break
if int(f) > g + 1 or int(f) < 0:
print f, q
if f == 'e':
print x, a[len(a) - 1] + 2
f = raw_input(o)
if -1 < int(f) < a[len(a) - 1] + 2:
g = 0
while a[g] <= int(f):
g += 1
if g == len(a):
break
print z, g, A, "up to", f
else:
print f, q
if f == 'f':
print t, r, a[len(a) - 1] + 1
f = raw_input(n)
g = raw_input(o)
if int(g) < int(f):
h = f
f = g
g = h
i = 0
if int(f) < 0 or int(g) > a[len(a) - 1] + 1:
print f, p, g, q
elif f == g:
print s, f, r, g
else:
for j in a:
if int(f) <= int(j) <= int(g):
i += 1
elif int(j) > int(g):
break
print z, i, A, "from", f, "thru", g
if f == 'v':
g = 0
h = 1
while f != 'q' and g < len(a):
i = h * 100
for g in range(100 * (h - 1), i):
if g == len(a):
i = len(a)
break
print a[g],
print u, str(100 * (h - 1) + 1) + v, str(i) + w
h += 1
if g == len(a):
break
f = raw_input("\nView the next 100 members or enter q to quit. ")
f = raw_input(m)
def run(a = 'r'):
while a is 'r':
a = raw_input("\nEnter r to run prime generator. ")
if a != 'r':
b = pg()
ui(b)
if __name__ == "__main__":
run()
print "\n" * 5, "Don't go away mad...Just go away.", "\n" * 5