Re: A different take on finding primes
1) google list of prime numbers 2) see Prime numbers list in the results (number 3 in the results) 3) click link that leads towww.prime-numbers.org I found 455042511 prime numbers in approx 15 seconds. Not bad at all. How about using http://www.sagemath.org/ (written in Python). sage: time primes_first_n(10^7); CPU times: user 4.36 s, sys: 2.43 s, total: 6.79 s Wall time: 6.88 s That used 3G of RAM, you could certainly go higher if you have more memory. aht -- http://mail.python.org/mailman/listinfo/python-list
Re: A different take on finding primes
On Tue, 17 Nov 2009 05:21, Tobiah wrote in comp.lang.python okgmm.17283$et3.3...@newsfe17.iad: Let me be clear, given 2min, how many primes can you find, they need not be in order or consecutive. Do they have to go from low to high? :( ) 1) google list of prime numbers 2) see Prime numbers list in the results (number 3 in the results) 3) click link that leads to www.prime-numbers.org I found 455042511 prime numbers in approx 15 seconds. Is that what you wanted? -- Nigel Rowe A pox upon the spammers that make me write my address like.. rho (snail) fisheggs (stop) name -- http://mail.python.org/mailman/listinfo/python-list
Re: A different take on finding primes
Let me be clear, given 2min, how many primes can you find, they need not be in order or consecutive. Do they have to go from low to high? :( ) -- http://mail.python.org/mailman/listinfo/python-list
A different take on finding primes
Out of pure curiosity I would like to compare the efficiency of different methods of finding primes (need not be consecutive). Let me be clear, given 2min, how many primes can you find, they need not be in order or consecutive. I have not seen any examples of this. I am assume the solution is different depending on the time give, 2min or 2 hours. I assume a sieve solution would be best for larger times. When the numbers get really large checking to see if they are a prime gets costly. So what do you think? *Vincent Davis 720-301-3003 * vinc...@vincentdavis.net my blog http://vincentdavis.net | LinkedInhttp://www.linkedin.com/in/vincentdavis -- http://mail.python.org/mailman/listinfo/python-list
Re: A different take on finding primes
Vincent Davis wrote: Out of pure curiosity I would like to compare the efficiency of different methods of finding primes (need not be consecutive). Let me be clear, given 2min, how many primes can you find, they need not be in order or consecutive. I have not seen any examples of this. I am assume the solution is different depending on the time give, 2min or 2 hours. I assume a sieve solution would be best for larger times. When the numbers get really large checking to see if they are a prime gets costly. So what do you think? *Vincent Davis 720-301-3003 * vinc...@vincentdavis.net my blog http://vincentdavis.net | LinkedInhttp://www.linkedin.com/in/vincentdavis The sieve can be very efficiently written, but you have to decide whether to optimize for memory size or for speed. At a minimum for size you need an object for each prime currently found, and you will be looking through that list for each new candidate. Incidentally this approach can be done without any division. If you have memory to burn, you make a bit array equal in size to the largest prime you expect to encounter. There are also good algorithms for deciding whether a number of a particular form is prime. For example, there's a test for numbers of the form 2**n + 1. And don't forget the Miller-Rabin test. DaveA -- http://mail.python.org/mailman/listinfo/python-list
