Re: A different take on finding primes

Discussion in 'Python' started by Dave Angel, Nov 15, 2009.

  1. Dave Angel

    Dave Angel Guest

    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 *
    >
    > my blog <http://vincentdavis.net> |
    > LinkedIn<http://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
     
    Dave Angel, Nov 15, 2009
    #1
    1. Advertising

  2. Dave Angel

    Tobiah Guest


    >> 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? :( )
     
    Tobiah, Nov 16, 2009
    #2
    1. Advertising

  3. > 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
     
    Anh Hai Trinh, Nov 18, 2009
    #3
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. AdrianK
    Replies:
    0
    Views:
    1,542
    AdrianK
    Jul 9, 2003
  2. someone else

    simple algorithm for finding primes

    someone else, Dec 8, 2003, in forum: C Programming
    Replies:
    32
    Views:
    1,417
    Chris Torek
    Dec 12, 2003
  3. Luc The Perverse

    [Algorithm] Sum of Primes < 1000000

    Luc The Perverse, Jan 5, 2007, in forum: Java
    Replies:
    50
    Views:
    1,907
  4. fieldfallow

    Way for computing random primes in standard C.

    fieldfallow, Feb 24, 2006, in forum: C Programming
    Replies:
    104
    Views:
    1,564
    David Holland
    Mar 13, 2006
  5. baltimoredude1

    Problem in Generating 1st 100 Primes

    baltimoredude1, Jul 28, 2006, in forum: C++
    Replies:
    18
    Views:
    472
    Panks
    Jul 31, 2006
Loading...

Share This Page