Message-ID: <39550689.9FC1C065@home.com>
From: Robin Johnson <robbat2 AT home DOT com>
Organization: Orbit Computers
X-Mailer: Mozilla 4.7 [en] (Win98; U)
X-Accept-Language: en,af,es
MIME-Version: 1.0
Newsgroups: comp.os.msdos.djgpp
Subject: Re: prime numbers
References: <8j2kh1$v5e$1 AT nnrp1 DOT deja DOT com>
Content-Type: text/plain; charset=us-ascii
Content-Transfer-Encoding: 7bit
Lines: 62
Date: Sat, 24 Jun 2000 19:05:33 GMT
NNTP-Posting-Host: 24.113.36.103
X-Complaints-To: abuse AT home DOT net
X-Trace: news1.rdc1.bc.home.com 961873533 24.113.36.103 (Sat, 24 Jun 2000 12:05:33 PDT)
NNTP-Posting-Date: Sat, 24 Jun 2000 12:05:33 PDT
To: djgpp AT delorie DOT com
DJ-Gateway: from newsgroup comp.os.msdos.djgpp
Reply-To: djgpp AT delorie DOT com

keep the credits to the code, don't rip it for your homework or something....

/* Quick Prime Finder by Robin Johnson
   24 June 2000

   This uses the sieve of Erosthenes method of finding primes.
   It's a memory hog sometimes. But I believe it's the quickest
   method of finding all the primes up to a particular number,
   as it avoids any recalculation involved in recursive methods.
   It believe it follow an O(n log n) growth. I think some 
   problems involved in this, namely the memory it takes up, 
   might be solvable by using BitSets or something similar, 
   as that could allow a memory saving of approx 8x.
*/

#include <iostream> //used for screen output

#define MAXPRIMES 40000 //just how many primes you want, provided you have
enough memory
#define FIRSTPRIME 1 //you can change this to 2 if you don't consider 1 to be a
prime

bool primes[MAXPRIMES]; //After the main section runs if(primes[i]) then i is
prime

void setup()
{ int i;
  primes[0] = false;
  primes[1] = false;
  for(i=FIRSTPRIME;i<MAXPRIMES;i++) primes[i]=true; //set every number to be
prime
 }

void calculate()
{ int i,j;
  for(i=2;i<MAXPRIMES;i++)
   { if(primes[i]) //if the current element is prime, then no multiples of it
are prime
      for(j=2*i;j<MAXPRIMES;j+=i) primes[j] = false;
    }
 }

void display()
{ int i;
  for(i=0;i<MAXPRIMES;i++)
   if(primes[i]) cout << i << endl;
 }

int main()
{ setup();
  calculate();
  display();
  return(0);
 }
-- 
Robin Hugh Johnson
"Robbat2"
QTOD: "I used to be an idealist, but I got mugged by reality."
E-Mail     : robbat2 AT orbis-terrarum DOT net
ICQ#       : 30269588 or 41961639
Home Page  : http://www.orbis-terrarum.net
Time Zone  : Pacific Daylight (GMT - 8)