Prime number algorithm in C

Discussion in 'C Programming' started by Cmorriskuerten, Nov 17, 2003.

  1. Cmorriskuerten

    CBFalconer Guest

    If you are willing to settle for the root of (<T>_MAX + 1), which
    must be of the form 2**n, simpler methods are available. At worst
    the root of 2 may be involved, for n odd.
    CBFalconer, Nov 21, 2003
    1. Advertisements

  2. Add parens ( (v) <= (n)/(v) ) to be safe in all uses.
    Or (in both versions) v * v <= n, which faster on nearly all
    platforms, often much faster.

    Or, less general, strength-reduce vsquared in the loop by adding 2*v-1
    for each increment, or 2*(v-1)+2*v-2 aka 4*v-4 for increment-by-2.

    - David.Thompson1 at
    Dave Thompson, Nov 22, 2003
    1. Advertisements

  3. Cmorriskuerten

    James Hu Guest

    Yes, thanks.
    But this is prone to overflow.

    -- James
    James Hu, Nov 22, 2003
  4. Cmorriskuerten

    Dan Pop Guest

    Show us the code, as a constant expression that can be evaluated at
    compile time.

    Dan Pop, Nov 24, 2003
  5. Cmorriskuerten

    CBFalconer Guest

    Adding the constant expression clause may be the rub, as offhand I
    do not know of any way of evaluating n above. Well, possibly a
    table, such as:

    #if INT_MAX == 32767
    # define n 16
    #elif INT_MAX == 65536
    # define n 17

    which doesn't appear overly attractive to me. :)

    Apropos to other arguments going on around here, things might have
    been simpler if the maximum bit weight (n above) had been
    specified as an exponent of two, rather than the <T>_MAX values.

    #define INT_MAX_BIT 30

    etc. This also leaves no holes and ambiguity to foster arguments
    CBFalconer, Nov 24, 2003
  6. Cmorriskuerten

    Dan Pop Guest

    And doesn't appear correct at all to me. Are you sure you're familiar
    with the powers of two? ;-)

    BTW, if you go this way, you can define the square root directly, instead
    of n.

    Dan Pop, Nov 25, 2003
  7. Cmorriskuerten

    CBFalconer Guest

    0.0002% is well within the expected experimental error :)
    CBFalconer, Nov 26, 2003
  8. Cmorriskuerten

    Dan Pop Guest

    Still missing the point. Your worst error above is 6.66% ;-)

    Dan Pop, Nov 26, 2003
  9. In general yes, though not if you are running the loop upwards (as was
    the previous-post case) and n is not almost UINT_MAX (which caveat I
    didn't state). But you can add a check for v <= sqrt_of_uint_max,
    which is actually a compile-time constant although it seems difficult
    to portably write it so, and I bet it's still faster than divide.

    - David.Thompson1 at
    Dave Thompson, Nov 27, 2003
  10. Cmorriskuerten

    James Hu Guest

    I don't doubt multiplication is faster than division on most platforms.
    But, I tend to first write code that I know will work first. I've been
    bitten by multiplication overflow too many times, I'm afraid.

    -- James
    James Hu, Nov 27, 2003
  11. Cmorriskuerten

    Paul Hsieh Guest

    Paul Hsieh, Nov 28, 2003
  12. Cmorriskuerten

    Eric Sosman Guest

    If you're using the `%' operator to check a candidate
    for divisibility, there's an excellent chance that the
    `/' to check for end-of-range is "free."

    for (div = 3; number / div >= div; div += 2)
    if (number % div == 0)

    Many compilers will perform just one division to generate
    both the quotient and the remainder.
    Eric Sosman, Dec 1, 2003
  13. Cmorriskuerten

    Ben Pfaff Guest

    In case it isn't smart enough, you can encourage it by using the
    standard C library div() function.
    Ben Pfaff, Dec 1, 2003
  14. Cmorriskuerten


    Jul 22, 2009
    Likes Received:
    Prime number algorithm in C++

    #include <iostream>
    using namespace std;

    void findPrime(int n)

    int i,j;
    int nn = n+1;
    bool array[nn];
    array[0] = false;
    array[1] = false;
    for (i=2; i<nn; i++)
    array = true;
    for(i=2; i<nn; i++)

    for (j=2; (i*j)<nn; j++)
    array[i*j] = false;

    for(i=0; i<nn; i++)
    cout<<i<<" is prime";


    int main()

    int n = 100;


    works for me!
    NaomiD, Jul 22, 2009
    1. Advertisements

Ask a Question

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

You'll need to choose a username for the site, which only take a couple of moments (here). After that, you can post your question and our members will help you out.