I'm not sure what your ultimate design objective (and balance) is to be, but you mentioned heavy use of caching, which is probably a very good idea. My thought, however, is that if hard drive space is plentiful, and processor cycles are not, you could cache all primes up to 100,000,000. According to this URL, there are about 5.76 million primes in the range under 100,000,000. If you can store each number in the 0 .. 100,000,000 range as a four-byte (32 bit) word, you'll need 21 Megabytes to cache all primes between 0 and 100,000,000.

Stored as a packed flat file of four-byte words, you could easily perform binary searches on the file, and thus determine primality in O(log N) time, where N is the number of primes you have cached. As for how to come up with this 21MB list, I'm sure there are sites out there that have already generated text-based lists of primes. Just convert that to packed words and presto.

...just thinking. Of course this assumes your design needs allow you all the storage space you want, and that you need the fastest possible solution. And it's not a complete solution, since there may still be times that you need to figure out primes past 100,000,000. For that, you'll still need a quick algorithm for testing primality.


Dave

In reply to Re: Math help: Finding Prime Numbers by davido
in thread Math help: Finding Prime Numbers by Ovid

Title:
Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post, it's "PerlMonks-approved HTML":


  • Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!
  • Titles consisting of a single word are discouraged, and in most cases are disallowed outright.
  • Read Where should I post X? if you're not absolutely sure you're posting in the right place.
  • Please read these before you post! —
  • Posts may use any of the Perl Monks Approved HTML tags:
    a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, details, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, summary, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr
  • You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)
            For:     Use:
    & &amp;
    < &lt;
    > &gt;
    [ &#91;
    ] &#93;
  • Link using PerlMonks shortcuts! What shortcuts can I use for linking?
  • See Writeup Formatting Tips and other pages linked from there for more info.