Mail Archives: djgpp/2000/06/24/15:15:21
MessageID:  <39550689.9FC1C065@home.com>

From:  Robin Johnson <robbat2 AT home DOT com>

Organization:  Orbit Computers

XMailer:  Mozilla 4.7 [en] (Win98; U)

XAcceptLanguage:  en,af,es

MIMEVersion:  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

NNTPPostingHost:  24.113.36.103

XComplaintsTo:  abuse AT home DOT net

XTrace:  news1.rdc1.bc.home.com 961873533 24.113.36.103 (Sat, 24 Jun 2000 12:05:33 PDT)

NNTPPostingDate:  Sat, 24 Jun 2000 12:05:33 PDT

To:  djgpp AT delorie DOT com

DJGateway:  from newsgroup comp.os.msdos.djgpp

ReplyTo:  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."
EMail : robbat2 AT orbisterrarum DOT net
ICQ# : 30269588 or 41961639
Home Page : http://www.orbisterrarum.net
Time Zone : Pacific Daylight (GMT  8)
 Raw text 