document.write( "<A HREF=/cgi-bin/jump-to-question.mpl?question=902616>Question 902616</A>: <I><SPAN STYLE=\"word-break: break-all;\"> I am trying to run a program that tells me how many prime numbers there are in a range of numbers. I run it in intervals of 10,000 to 100,000. How long would the program take to determine all the prime numbers between 2 and the largest known primes (with about 13 million digits)<BR>\n" );
document.write( "for 10,000 it took 0.494s<BR>\n" );
document.write( "for 20,000 it took 1.100s<BR>\n" );
document.write( "for 30,000 it took 1.965s<BR>\n" );
document.write( "for 40,000 it took 3.149s<BR>\n" );
document.write( "for 50,000 it took 4.579s<BR>\n" );
document.write( "for 60,000 it took 6.305s<BR>\n" );
document.write( "for 70,000 it took 8.108s<BR>\n" );
document.write( "for 80,000 it took 10.343s<BR>\n" );
document.write( "for 90,000 it took 12.560s<BR>\n" );
document.write( "for 100,000 it took 15.091s\r<BR>\n" );
document.write( "\n" );
document.write( "According to what I have now, How would I find the solution? I do understand that this will take a very long time, but how long exaclty </SPAN>\n" );
document.write( "</I><HR><TABLE width=100%><TR><TD><B><A HREF=http://www.algebra.com/>Algebra.Com's</A> Answer #547447 by </B><A HREF=/tutors/aboutme.mpl?userid=richard1234><B>richard1234(7193)</B></A><img src=\"/images/stars/stars-13.gif\" alt=\"\" >&nbsp;<A HREF=/tutors/aboutme.mpl?userid=richard1234><IMG SRC=http://www.algebra.com/images/aboutme-small.gif BORDER=0 alt=\"About Me\" VALIGN=MIDDLE></A>&nbsp;<IMG SRC=http://www.algebra.com/cgi-bin/show-face.mpl?user=richard1234><BR>You can <A HREF=\"/cgi-bin/embed-solution.mpl?show=1&solution=547447\">put this solution on YOUR website!</A><BR><SPAN STYLE=\"word-break: break-all;\"> That depends on the asymptotic runtime of your prime-checking algorithm, and you would also need a ton of space.\r<BR>\n" );
document.write( "<BR>\n" );
document.write( "\n" );
document.write( "By the way, 15 seconds to check all primes up to 100000 seems pretty slow. I was able to create a list of primes up to 100000 in about 0.5 sec. Here is some example Python code:\r<BR>\n" );
document.write( "\n" );
document.write( "def prime(n): #this one is on Wikipedia<BR>\n" );
document.write( "___if n < 1: return False<BR>\n" );
document.write( "___if not n%2 or not n%3: return False\r<BR>\n" );
document.write( "\n" );
document.write( "___for i in xrange(5, int(n**0.5 + 1), 6):<BR>\n" );
document.write( "______if not n%i  or not n%(i+2): return False<BR>\n" );
document.write( "___return True\r<BR>\n" );
document.write( "<BR>\n" );
document.write( "\n" );
document.write( "Then to generate a list of primes:<BR>\n" );
document.write( "def primeslist(n): #creates a list of primes <= n:<BR>\n" );
document.write( "___l = []<BR>\n" );
document.write( "___for i in range(1, n+1):<BR>\n" );
document.write( "______if prime(i): l.append(i)<BR>\n" );
document.write( "___return l\r<BR>\n" );
document.write( "\n" );
document.write( "Of course there are faster methods but it only took 0.5 seconds to create the list.\r<BR>\n" );
document.write( "<BR>\n" );
document.write( "\n" );
document.write( " </SPAN>\n" );
document.write( "</TD></TR></TABLE>\n" );