一些基本且低效的素數生成演算法
(重定向自一個更有效的素數生成演算法)
 |
一位華夏公益教科書使用者認為此頁面應該拆分為更小的頁面，內容更集中。 你可以透過將這個大頁面拆分成更小的頁面來幫助。請確保遵循命名策略。將書籍分成更小的部分可以提供更多焦點，並允許每個部分都能做好一件事，這對每個人都有益。 |
在任何典型的程式語言課程中，學生都會得到一個專案，編寫一個生成素數的程式。這被認為是一個相對簡單的任務，在課程的前幾周內就會被分配。我相信你已經知道，一些簡單有效的演算法可以用在不到幾分鐘的時間內完成這個任務。在以下示例中，我將使用 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 的多少倍。請注意，程式執行的時間越長，效率就越顯著。
感謝您抽出時間研究該演算法，希望它能激發您的靈感。如果您選擇將該演算法翻譯成其他程式語言，請將您的作品的副本傳送電子郵件至 cfo@mfbs.org。
好吧，所有步驟都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