You start by taking the int of the square root of the number you want to test for prime. This is the largest number that could potentially divide cleanly into your number without a smaller number also dividing cleanly. Then you check all the primes currently stored, up to that max, to see if they divide into your number cleanly. If they do, you return 0 - no further processing is necessary. If you reach a prime larger than max, you return 1 - the number is a prime.

But what if there aren't enough primes in your array to check all the way up to max? You need to calculate those primes so you can check them. For all numbers from the current max stored prime + 1 to the square root of the potential prime, you check each number to see if it's a prime - using the same function! You add these primes to the stored primes array, and also check each one to see if it divides cleanly into your number. If it does divide cleanly, no further calculations are necessary, and the function returns 0.

Bottom line, only necessary calculations are made (as far as I can tell), minus a few minor tweaks such as skipping even numbers.

In reply to Re: Primes. Again. by TedPride
in thread Primes. Again. by Andrew_Levenson

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.