Finding and Printing prime numbers using arrays

**Sektor** · 12-10-2003

Hi everyone. I'm trying to write a code which will find and print out every prime number between 1 and 1000 using a 1000 element array (NOTE: I am not allowed to use the prime number function).
Problem is, my program outputs EVERY number from 1-1000. Please take a look at my program and help me fix it (im farely new to C++)

Code:

// 4.29
// Prime Number

#include <iostream>

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

int main()
{
	const int arraysize = 1000;
		int x, a[arraysize], b;

	for (x=0; x < arraysize; x++)

		a[x] = 1;

	for (x=2; x < arraysize; x++)
	{
		if ( arraysize ==1)
		{
			while ( b < arraysize )
			{
		b = x;
				x = x + b;

			a[b] = 0;

			}
		}
	}

	a[1] = 0;
	cout << " here are your prime numbers from 1000 ";

	for (int c = 0; c < arraysize; c++)
	{
		if (a[c] = 1)
			cout << c << " ";
	}

	return 0;

**joshdick** · 12-10-2003

You didn't initialize b.

I don't see how your algorithm is supposed to find prime numbers.

To find primes using an array, you could use Eratosthenes's sieve. Here's a webpage about it: http://www.acypher.com/creator/Worlds/PrimeNumber/

To implement this, use an array of booleans.

**Sektor** · 12-10-2003

That's the problem... I dont know how to do it really... can you guide me through it?
I'll try and start the program over... I think I'd need modulus for it.

Code:

ode:
// 4.29
// Prime Number

#include <iostream>

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

int main()
{
	const int arraysize = 1000;
		int x, a[arraysize], b;

	for (x=0; x < arraysize; x++)

 //would this work??
 if (x % (x-2) != 0) // number is prime?

**joshdick** · 12-10-2003

Let's get back to basics. A number p is a prime number if an only if it is divisible only by one and itself. To test this, you will have to test whether p is divisible by any other numbers. Here's a nieve algorithm to test if p is prime:

Code:

bool isprime(int p)
{
  for(int i = 2; i < p; ++i)
    if(p % i == 0)
      return false;
  return true;
}

I say that that's a nieve algorithm because it could be optimized quite a bit. I'll leave it to you to figure out how to improve on that algorithm.

The above is an algorithm for determining if a single number p is prime. If you have to find every prime number less than 1000, though, the Sieve of Eratosthenes would be a better choice.

Declare an array of a thousand booleans.
For all numbers n[i] in that array, set n[i] * k to false for all k > 1.

In simpler terms, imagine just a list of the first 1000 numbers on a sheet of paper. Start with multiples of 2. Cross out every multiple of 2 (besides 2). Then, cross out every multiple of 3 (besides 3). Don't worry about 4 because it's already crossed out. Continue on with multiples of five. Then, multiples of seven, multiples of eleven, ...
When you're done with all of the necessary crossing out for all 1000 numbers, the numbers that aren't crossed out are prime numbers. This is the Sieve of Eratosthenes.

My suggestion is to try to implement that sieve in C++.

**Zach L.** · 12-10-2003

Let's get back to basics. A number p is a prime number if an only if it is divisible only by one and itself. To test this, you will have to test whether p is divisible by any other numbers.

Just make sure not to include 1 in your list of primes.

Yeah, for small primes (which those under 1000 certainly fall under), joshdick's method is probably the most practical.

**Sektor** · 12-11-2003

hehe, it came out the question itself was asking me to use the Sieve of Eratosthenes to carry out this program

. Thanks, I'll try my best to work this out (im still new at programming)

Thread: Finding and Printing prime numbers using arrays

Thread Tools

Search Thread

Display

Finding and Printing prime numbers using arrays

Similar Threads

Finding a directory, and printing whats in it