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>
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)

- Raw text -