From:	Charles Krug <charles AT pentek DOT com>
Newsgroups:	comp.os.msdos.djgpp
Subject:	Prime number generation
Date:	Wed, 13 Aug 1997 10:19:06 +0100
Lines:	71
Message-ID:	<33F17C09.1CE7@pentek.com>
NNTP-Posting-Host:	mail.pentek.com
Mime-Version:	1.0
To:	djgpp AT delorie DOT com
DJ-Gateway:	from newsgroup comp.os.msdos.djgpp

I'm generating a rather long portable list of prime numbers using this
program.

/********************************************************************
* primex.cc -- generates a list of primes                           *
********************************************************************/

unsigned long primes[32768],          // array of primes
         curr_value(3),          // current value being tested
         first_empty(1),         // first empty member
         curr_prime,             // the current prime
         prime_index;            // present offset into primes

main()
{
    // initialize first prime number.
    primes[0] = 2;

    while (first_empty < 32768)
    {
        // initialize inner loop
        prime_index = 0;

        while (prime_index < first_empty)
        {
            curr_prime = *(primes + prime_index);

            /* Compare to the current prime
                in this case, we've found a prime factor */
            if (curr_value % curr_prime == 0)
                break;

            // We may be at the end of our rope here
            else
            {
                ++prime_index;    // update the index
                if (((curr_prime * curr_prime) > curr_value) ||
                    (prime_index == first_empty))

                // We have a winner
                {
                    *(primes + first_empty) = curr_value;
                    ++first_empty;
                    // write to the file
                    break;
                }
            }

        }
        curr_value += 2;
    }
    return(0);
}

The output is the following c source file:

/* primes.c -- list of 32767 prime numbers */
long primes[32768] = {2, 3, 5, 7, 11, 13,  . . . etc. };

(Yes, Chris, I tested my conditionals and they work as expected. :-) )

Question:  Is there an alternative algorithm for generating a list of
primes?  If so, what are the merits and demerits of the alternative
approach.

-- 
Charles Krug, Jr.

> In an infinite, non repeating set,
> any finite subset will be found an
> infinite number of times. -- Like Kevin Bacon movies
ogramming doesn't have to be hard, but there's no law that says it has
to be effortless either.

There. Just had to get that off my chest :)

-- 
------------ Elliott Oti ---------------
   ------------- http://www.fys.ruu.nl/~oti  ---------

- Raw text -