Efficient Prime Number Generating Algorithms

From Wikibooks, open books for an open world
Jump to: navigation, search

PGsimple1[edit]

In any typical programming language course, the student gets a project to write a program that generates prime numbers. This is considered to be a relatively easy task which is assigned within the first few weeks of the course. As I'm sure you are aware, a few simple and effective algorithms can be used to complete the assignment within as little as a few minutes. In the following examples, I will be using the Python2.5 programming language to demonstrate such algorithms and compare their efficiencies.

The first algorithm we shall consider will begin with the integer 2 and proceed to select each successive integer as a potential prime, (pp), checking for primacy by testing to see if it can be factored by any previously identified primes, then storing each newly verified prime in a prime set (ps) array.

	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: ps.append(pp)
	return ps

Note: The code given above does not constitute a complete program. See Appendix A for a complete program including a user interface.

Such a rudimentary algorithm takes a strictly brute force approach to effectively achieve the goal of identifying each prime number and storing it in an array. I am sure you would agree that this is also about the least efficient means of generating prime numbers. As we shall see, using elements of sieving processes will increase the efficiency of our program while avoiding the time consuming property of a true Sieve of Erastothenes which selects every consecutive integer as a potential prime before identifying it as factorable and eliminating it as a prime number, much the way PGsimple1 has done.

Runtime Data

primes          pgsimple1 
up to           takes
 
100             .00100 sec
1000            .02800 sec
10000           1.6980 sec
100000          130.44 sec
1000000         10732  sec

These are the best time results taken from 5 test runs at each limit.

This table records the runtimes for pgsimple1 up to each limit indicated. Please accept that these runtimes and all of the runtimes given throughout this document may differ somewhat from those which you may get running the same program on a computer with different hardware or software as mine, which has an AMD Turion 64 1.9GHz with 2GB RAM, 160GB HDD and Windows Vista.

PGsimple2[edit]

A first step at improving this algorithm might be efficiently selecting potential primes. It is most common to see such a device in algorithms which start with the integer 3 and proceed by selecting successive potential primes through the odd integers only. This reduces by half the total number of potential primes which must be tested.

	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

Now, brute force has been augmented by some simple logic to significantly improve efficiency, reducing the number of potential primes by half.

Runtime Data

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           ~

These are the best time results taken from 5 test runs at each limit.

This table records the runtimes for pgsimple2 and how many times faster it completes the run up to each limit compared to pgsimple1. Note that the efficiency remains close to double that of pgsimple1 at any limit. Even at this speed, it is still quite impractical to generate 8 digit primes or more. But, I did it just to see how long it would take.

PGsimple3[edit]

The next most obvious improvement would probably be limiting the testing process to only checking if the potential prime can be factored by those primes less than or equal to the square root of the potential prime, since primes larger than the square root of the potential prime will be complementary factors of at least one prime less than the square root of the potential prime.

	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

This algorithm makes truly significant strides in efficiency and, at this point, most programmers have exhausted their ability or desire to continue improving the efficiency of the prime number generator, but we shall go on.

Runtime Data

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            ~                            ~

These are the best time results taken from 5 test runs at each limit.

This table records the runtimes for pgsimple3 and how many times faster it completes the run up to each limit compared to pgsimple1 and pgsimple2. Note that the longer the program is run, the more significant the efficiency becomes.

PGsimple4[edit]

Recognizing that by using a skip number of 2 to select only odd potential primes, it is no longer necessary to test potential primes against all the primes less than the square root of the prime, as none of them can be factored by 2. Therefore, we can remove the first prime number from the set of primes which we test potential primes against. This requires dividing the prime set (ps) array into excepted prime (ep) and test prime (tp) arrays, then recombining them at the end to send the complete set back to the function call.

	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

In the next version it will be shown why we put the skip number (2) into a skip set (ss) array.

Runtime Data

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

These are the best time results taken from 5 test runs at each limit.

This table records the runtimes for pgsimple4 and how many times faster it completes the run up to each limit compared to pgsimple3.

What improvement in efficiency? Note that there is only a marginal increase in efficiency compared to pgsimple3. Worry not, increases in efficiency multiply as more primes are eliminated from the testing process in the more advanced version of the program which I will show you next.

PG7.8[edit]

This algorithm efficiently selects potential primes by eliminating multiples of previously identified primes from consideration and minimizes the number of tests which must be performed to verify the primacy of each potential prime. While the efficiency of selecting potential primes allows the program to sift through a greater range of numbers per second the longer the program is run, the number of tests which need to be performed on each potential prime does continue to rise, (but rises at a slower rate compared to other algorithms). Together, these processes bring greater efficiency to generating prime numbers, making the generation of even 10 digit verified primes possible within a reasonable amount of time on a PC.

Further skip sets can be developed to eliminate the selection of potential primes which can be factored by each prime that has already been identified. Although this process is more complex, it can be generalized and made somewhat elegant. At the same time, we can continue to eliminate from the set of test primes each of the primes which the skip sets eliminate multiples of, minimizing the number of tests which must be performed on each potential prime. This example is fully commented, line by line, with some explanation to help the reader fully comprehend how the algorithm works. A complete program including a user interface, but without the comments, can be found in Appendix B.

Please disregard syntactical errors which occur in the user interface such as “the 1th prime”, instead of “1st”, and the inclusion of the last prime generated in the completed array even though it may be larger than the user defined limit. These errors can easily be corrected at the convenience of the student programmer, but were not necessary to illustrate the performance of the algorithms. I apologize for any confusion or inconvenience this may have caused the reader.

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. """

Runtime Data

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            ~                            ~

These are the best time results taken from 5 test runs at each limit.

This table records the runtimes for pg7.8 and how many times faster it completes the run up to each limit compared to pgsimple1 and pgsimple4. Note that again the longer the program is run, the more significant the efficiency becomes.

A note from the author[edit]

Thank you for taking the time to study the algorithm and I hope that it has inspired you. If you choose to translate this algorithm into another programming language, please email a copy of your work to cfo@mfbs.org.

A note from the prime-number-best-algorithm owner[edit]

Well, all steps are ok, but you stop at the very beginnig; as long as you can state that all 2N with N>1 are not primes you can also state that all primes except 3 are not in the form 3N and so on.

It lead at first step to the known primes form of 6N±1 (that is elegant but wrong, the really form is 6N+1 or 6N+5) but you can do better, as long you use 30N+1, 30N+7, 30N+11 ..... 30N+29 or even better with 210N+1, 210N+11, 210N+13 ...... 210N+209

in short : exist an algorithm to reduce the "search field" in a smart way, using 1*1, 1*2, 1*2*3, 1*2*3*5, 1*2*3*5*7 .... as "base" and a list of "displacements" to add.

but the speed is still compromised by the presence of multiple, always growing, "sqrt" and "div" (or better "mod") operations.

the sqrt operations can be "reversed", simply doing a N^2 that limits validity of your tests : the benefit in time-terms is great!

also "module" ops can be avoided, but the trick is a little bit long to be wrote, will do sometime in future

in short : there is no need to calculate primes as long as you can guess them and are able to distinguish between "real" and "fake" ones.

regards

$witch

Appendix A[edit]

#! /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': return
		b=pg()
		ui(b)
if __name__ == "__main__":
	run()
	print "\n"*5,"Don't go away mad...Just go away.","\n"*5
	raw_input()


Appendix B[edit]

#! /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': return
		b=pg()
		ui(b)
if __name__ == "__main__":
	run()
	print "\n"*5,"Don't go away mad...Just go away.","\n"*5
	raw_input()