Prime Numbers from 0-300

Zorachus · #1 11-Jul-2005, 09:09

I have been trying to figure out what is wrong with this code ever since writing it at a computer camp at Transylvania. There are no syntax errors; everything seems like it should work fine. However, when I run it, I get the annoying "This program has encountered a problem and needs to close" box, which I believe is called a runtime error. If anybody could, please take a look at this code and help me out with it. The code is designed to print a list of the prime numbers from 0-300 using the Sieve of Erastophanes.

CPP / C++ / C Code:

/*/  Lists prime numbers from 0 to 300 /*/
#include <iostream>
using namespace std;
int main()
{
int a,b,c,d,e;
a = 2;
d = a;
int prime[298];
for (b=0; b<=297; b++)
    {
          prime[b] = (b+2);
    }  
    b=1;
for(b=1; b<10; b++)
{
         cout << b << " first for loop" << endl;
    for (c=0; c<=297; c++)
        {
        cout << "                      " << c << " for loop" << endl;
        d=a+d;
        prime[d]=0;
        }
    a++;
    d=a;
    b++;
}
while(b != 9)
cout << "Prime numbers from 0-300: " << endl;
for (b=0; b<=297; b++)
    {
    if (prime[b] !=0)
       cout << prime[b] << endl;
    }
system ("pause");
return 0;
}

Zorachus · #2 11-Jul-2005, 09:16

sorry for the double post... I forgot to mention that when using the couts in the for loops to watch the progress, i noticed that the code terminates after approximately halfway through the third outer loop. Is it possible that I am just trying to do too many things at once?

Dave Sinkula · #3 11-Jul-2005, 09:49

Infinite loop here?

CPP / C++ / C Code:

   while ( b != 9 )
      cout << "Prime numbers from 0-300: " << endl;

Zorachus · #4 11-Jul-2005, 10:50

blah
That was just a do/while loop that I neglected to completely remove, it is not in the actual code. The program terminates specifically on outer loop 3, inner loop 113.
Sorry... ignore that while.

davekw7x · #5 11-Jul-2005, 11:03

Quote:

Originally Posted by Zorachus

blah
That was just a do/while loop that I neglected to completely remove, it is not in the actual code. The program terminates specifically on outer loop 3, inner loop 113.
Sorry... ignore that while.

Where it actually terminates is, in this case, system-dependent. The reason that it terminates is that you address memory out-of-range.

To see why the program bombs, you can do something like this:

CPP / C++ / C Code:

// Print out the value of any out-of-range index and terminate the program

        d=a+d;
        if ((d < 0) || (d > 297)) {
          cout << "a = " << a << ", b = " << b << ", c = " << c << ", d = " << d << endl;
          exit(1);
        }
        prime[d]=0;

I am having a little problem seeing what the heck this has to do with prime numbers or the Sieve of Whats-His-Name. Maybe you could explain???

Regards,

Dave

Zorachus · #6 11-Jul-2005, 12:13

thanks for the tip, dave...
Here is the basic rundown on the sieve:
The sieve is used to find prime numbers using a simple method. Starting with two (because 1 is not technically a prime number), you add two to itself until you have reached the desired number (In this case, 300). You then eliminate all of those numbers. Confused?

2= prime; divisible by only one and itself.
2+2=4; not prime, divisible by itself, one, and two
2+2+2=6; not prime, divisible by itself, one, three, and two

This eliminates all numbers divisible by two.
You do the same thing with three:
3=prime
3+3=6; not prime
3+3+3=9; not prime

You continue this until you reach 300, then go through the same method with 4,5,6, etc., all the way up to 9. In this case, for every number that this method covers, I stored a 0 to that number's spot in the array (ex: for the number 9, which would be at spot 6 in the array (since i started with two and the array starts at 0) i would store 0 to spot six, indicating that that spot is not prime.

This would leave all prime numbers; nothing doubles to equal 5, for example, making it prime.

That is the basic concept behind the sieve. I'm sorry if i confused the hell out of everyone.

BY THE WAY: It's the sieve of aristophanes, I got it wrong earlier, my apologies.

Dave Sinkula · #7 11-Jul-2005, 12:25

Quote:

Originally Posted by Zorachus

BY THE WAY: It's the sieve of aristophanes, I got it wrong earlier, my apologies.

Eratosthenes?

Zorachus · #8 11-Jul-2005, 12:27

You would think someone who gets so many things wrong would be a horrible programmer... and you are probably right. Yes, that's the one. Too many Greeks to keep track of.

That is the algorithm I used, essentially, though I did pull mine out of my own head, which is probably why there is an error.

davekw7x · #9 11-Jul-2005, 12:50

Quote:

Originally Posted by Zorachus

thanks for the tip, dave...
Here is the basic rundown on the sieve:
The sieve is used to find prime numbers using a simple method. Starting with two (because 1 is not technically a prime number), you add two to itself until you have reached the desired number (In this case, 300). You then eliminate all of those numbers. Confused?

2= prime; divisible by only one and itself.
2+2=4; not prime, divisible by itself, one, and two
2+2+2=6; not prime, divisible by itself, one, three, and two

This eliminates all numbers divisible by two.
You do the same thing with three:
3=prime
3+3=6; not prime
3+3+3=9; not prime

You continue this until you reach 300, then go through the same method with 4,5,6, etc., all the way up to 9. In this case, for every number that this method covers, I stored a 0 to that number's spot in the array (ex: for the number 9, which would be at spot 6 in the array (since i started with two and the array starts at 0) i would store 0 to spot six, indicating that that spot is not prime.

This would leave all prime numbers; nothing doubles to equal 5, for example, making it prime.

That is the basic concept behind the sieve. I'm sorry if i confused the hell out of everyone.

BY THE WAY: It's the sieve of aristophanes, I got it wrong earlier, my apologies.

Well, I know what the Sieve of Eratosthenes is. Your narrative is pretty close to my understanding.

I just don't see which parts of your program implement any part of the Sieve.

Here's how I would look at it:

First of all, we need an array with the index values equal to the highest number we will consider. So if we are going to test for prime numbers less than or equal to 300, we would have an array with index values up to 300. Now, it seems that you already know some values, say 300 and 299, and 298 are not primes, the array can go to 297. I'm with you so far.

Now this array will keep track of whether an integer with a particular index is prime or not. Let's suppose we use 0 to indicate "not prime", and 1 to indicate "prime". I am going to call the array x, and I am going to give it a dimension of 300.

So, at the end of the run, x[2] = 1, x[3] = 1, x[4] = 0, x[5] = 1, x[6] = 0, etc.

Here's a way to approach the problem:

Initialize the array to indicate primes:
go through the array: i = 2, 3, ..., 300, and set x[i] = 1.

Now heres the Sieve: (We make a loop to implement the following steps.)

First, eliminate multiples of 2:
go through the array: i = 4, 6, 8, ..., and set x[i] = 0.

Then, eliminate multiples of 3:
go through the array: i = 6, 9, 12, 15, ... and set x[i] = 0.

Continue for multiples of 4, 5, ... 150.

(Why don't we have to consider numbers greater than 150? Because no number greater than N/2 can be a proper factor of N.)

After the above steps have been completed, print the results.

Go through the array: i = 2, 3, ..., 300 and print out the value of i for which x[i] is not zero.

Regards,

Dave

[edit]
Further performance improvements are possible, but first of all: get the thing working.
I would also put in a counter to see how many non-zero elements there are after the Sieve. For this case, the number of primes less than or equal to 300 is equal to 62.

I would use test cases less than 300 do debug the program. (That way I could print out everything during and after the loops. (That means that instead of hard-coding 300 as the size of the array and various loop limits, I might do something like this at the start of the program:

CPP / C++ / C Code:

#define HIGHEST 300
char prime[HIGHEST+1];
  for (i = 2; i <= HIGHEST; i++) {
    prime[i] = 1;
  }

Then I could recompile and run it with HIGHEST defined to be 10, 20 or whatever.

The I could get results like this

Number of primes <= 10 is 4

etc.
[/edit]

Zorachus · #10 11-Jul-2005, 13:28

Dave,
Thanks to your help and a little experimentation, I have come up with the working code:

CPP / C++ / C Code:

/*/  Lists prime numbers from 0 to 300 /*/
#include <iostream>
using namespace std;
int main()
{
int b,c;
int prime[298];
for (b=0; b<=297; b++)
    {
          prime[b] = (b+2);
    }  
/*/for(b=2; b<150; b++)
{
    for (c=(b+b); c<=299; c=c+b)
        {
        prime[c-2]=0;
        }
   
}
/*/
cout << "Prime numbers from 0-300: " << endl;
for (b=0; b<=297; b++)
    {
    if (prime[b] !=0)
       cout << prime[b] << endl;
    }
system ("pause");
return 0;
}

I've been working on this code for a while, thanks for the help. The actual sieve is in comments.

Thread Tools	Search this Thread
Show Printable Version Email this Page	Search this Thread: Advanced Search
Rate This Thread
Rate This Thread:

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Binary number systems: BCD, twos complement, ones complement, etc.	machinated	Miscellaneous Programming Forum	6	08-Feb-2006 10:51
Linear Search	eccoflame	C Programming Language	3	19-Apr-2005 08:36
prime numbers	quasimof	C++ Forum	1	01-Nov-2004 19:35
[CONTEST?]Data Structure Test	dsmith	C Programming Language	2	06-Jun-2004 15:13
Help w/ prime # determination	crystalattice	C Programming Language	17	18-Apr-2004 21:43