Re: [Dev-C++] Prime number examples

[Jason H. <jas...@bt...>]

Prime number examplesUm... I think you're off to a bad start then, cos =
there is a mistake in the code you have supplied. You don't want to =
declare a const array because you won't be able to modify it. As the =
array values will be only 1 or 0 (true or false) then I recoment using =
an array of bool.

The steps you need to take are described to you in the question, and I =
don't want to supply the program for you, after all it is an exercise =
for you. I'll try to clarify if tfor you.

Step (a) is the initialisation step which I will help you with:

#include <iostream>

using std::cout;
using std::endl;

void main()
{
    const int MAX_PRIME =3D 1000; // a constant - change this value to =
increase or
        // decrease the number of primes to calculate.=20
        // By doing it this way you don't have to go through a program
        // and change the same value several times if you want more =
primes.

    // Create and initialise primes array (step a)
    bool primes[MAX_PRIME];
    primes[0] =3D false; // ignore array element 0
    for(int index =3D 1; i < MAX_PRIME; ++i)
        primes[index] =3D true; // true or 1: it's up to you

    // Calculate primes using Sieve of Eratosthenes (b)

        // you do this bit
   =20
    // Display prime numbers

        // go for it!
}

Step (b):
What you need to do is find an index at which the value is true (1) =
starting from index 2. To find the value it's best to go through the =
array from the beginning point until you find it. This sugests a loop of =
some kind with a conditional (if) statement to detect the true value. =
You then need to go through the array from that point and set to false =
(0) every multiple of the true index you just found. Another loop.
This means that you actualy have a loop within a loop. You need to =
decide upon which looping construct you will use and make sure you =
figure out the proper exit conditions for the loops (clue: MAX_PRIME), =
an easy way of making multiples is to repeatedly add the value to a =
second index, rather than actualy performing multiplication.
The two loops should exit when all of the array has been gone through.

The trick is that the inner loop makes false values you can ignore in =
the outer loop.

One of the keys to understanding this approach is to understand that the =
prime numbers aren't actualy stored within in the array, the index of =
the array represents the prime number, the value at a particular index =
is telling you whether it's index is prime or not. In a way you are =
asking a question of the array. You say "Is the number 7 prime?" and you =
would look at the value at index 7 of the array (primes[7]) and it =
should answer with "True" or the value 1 which means true. I hope I'm =
not sounding silly now?

The third step is to display the prime values. All you need to do is run =
through the array like you did when initialising it, and print out all =
the index's who's corresponding values are true. i.e. IF value AT index =
IS true THEN PRINT index.

Hope this helps,

Jason.

P.S. I've not tested the code I've supplied so you may get syntax errors =
with it.
  ----- Original Message -----=20
  From: Mitchell, Tamra (HNA)=20
  To: 'dev...@li...'=20
  Sent: Tuesday, February 12, 2002 6:00 PM
  Subject: [Dev-C++] Prime number examples


  Does any one have sample programs arrays and prime numbers?=20

  I have a program Due Friday and am totally confused.=20

  Can anyone point me in the right direction=20

  Here is my exercise.=20

  (The Sieve of Eratosthenes) A prime integer is any integer that is =
easily divisible only by itself and 1. The Sieve of Eratosthenes is a =
method of finding prime numbers.  It operates as follows

          a).  Create an array with all elements initialized to 1 =
(true).  Array elements with prime subscripts will remain 1.  All other =
array elements will eventually be set to        zero.

         =20
          b).  Starting with array subscript 2 (subscripts 1 must be =
prime), every time an array element is found whose value is 1, loop =
through the remainder of the array and   set to zero every element whose =
subscript is a multiple of the subscript for the element with value 1.  =
For array subscript 2, all elements beyond 2 in the array that  are =
multiples of 2 will be set to zero(subscripts 4, 6, 8, 10, etc.) for =
array subscript 3, all elements beyond 3 in the array that a are =
multiples of 3 will be set to zero    (subscripts 6, 9, 12, 15 etc) and =
so on.

  When this process is complete, the array elements that are still set =
to one indicate that the subscript is a prime number.  These subscripts =
can then be printed.  Write a program that uses an array of 1000 =
elements to determine and print the prime numbers between 1 and 999.  =
Ignore element 0 of the array.

   This is what I have so far=20

  #include<iostream>=20

  using std::cout;=20
  using std::endl;=20

  #include<iomanip>=20

  int main()=20
  {=20
          const int i[1000];=20
  }=20

  Not much.=20

  Tamra Y. Mitchell=20
  Heinz North America=20
  Database & Operating Systems  Analyst=20
  (412) 237-5232  Work=20
  (412) 996-9078  Cell Phone=20