From: "David Kinder" <D DOT Kinder AT btinter-remove-to-reply-net DOT com>
Newsgroups: comp.os.msdos.djgpp
Subject: Re: prime numbers
Date: Sat, 24 Jun 2000 22:53:43 +0100
Organization: BT Internet
Lines: 37
Message-ID: <8j3akc$itd$1@neptunium.btinternet.com>
References: <8j2kh1$v5e$1 AT nnrp1 DOT deja DOT com>
NNTP-Posting-Host: host5-99-55-158.btinternet.com
X-Priority: 3
X-MSMail-Priority: Normal
X-Newsreader: Microsoft Outlook Express 5.00.2919.6600
X-MimeOLE: Produced By Microsoft MimeOLE V5.00.2919.6600
To: djgpp AT delorie DOT com
DJ-Gateway: from newsgroup comp.os.msdos.djgpp
Reply-To: djgpp AT delorie DOT com

> how can I write a program that displays all the prime numbers (numbers
> that can only be divided by themselves and one) from 1 to N ??

This isn't really a DJGPP question. However, since I'm not sure quite
where on Usenet it would be on-topic:

A quick and easy way to get primes from 1 to n is the sieve of Eratosthenes.
To quote from a website I found by searching for "Eratosthenes"
(http://www.math.utah.edu/~alfeld/Eratosthenes.html):


 A prime number is a natural number greater than 1 that can be divided without
 remainder only by itself and by 1. Natural numbers n that can be divided by a
 number less than n and greater than 1 are composite numbers. The Sieve of
 Eratosthenes identifies all prime numbers up to a given number n as follows:

 1. Write down the numbers 1, 2, 3, ..., n. We will eliminate composites by
    marking them. Initially all numbers are unmarked.
 2. Mark the number 1 as special (it is neither prime nor composite).
 3. Set k=1. Until k exceeds or equals the square root of n do this:
    Find the first number in the list greater than k that has not been
    identified as composite. (The very first number so found is 2.) Call
    it m. Mark the numbers 2m, 3m, 4m, ... as composite. (Thus in the
    first run we mark all even numbers greater than 2. In the second run
    we mark all multiples of 3 greater than 3.)
    m is a prime number. Put it on your list.
    Set k=m and repeat.


This is a pretty good algorithm for reasonably small values of n. For
very large n you'll have to look up a more complex routine in a maths
textbook.

David