Finding and Printing prime numbers using arrays

This is a discussion on Finding and Printing prime numbers using arrays within the C++ Programming forums, part of the General Programming Boards category; Hi everyone. I'm trying to write a code which will find and print out every prime number between 1 and ...

  1. #1
    Registered User
    Join Date
    Dec 2003
    Posts
    7

    Finding and Printing prime numbers using arrays

    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;

  2. #2
    Senior Member joshdick's Avatar
    Join Date
    Nov 2002
    Location
    Phildelphia, PA
    Posts
    1,146
    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.
    FAQ

    "The computer programmer is a creator of universes for which he alone is responsible. Universes of virtually unlimited complexity can be created in the form of computer programs." -- Joseph Weizenbaum.

    "If you cannot grok the overall structure of a program while taking a shower, you are not ready to code it." -- Richard Pattis.

  3. #3
    Registered User
    Join Date
    Dec 2003
    Posts
    7
    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?

  4. #4
    Senior Member joshdick's Avatar
    Join Date
    Nov 2002
    Location
    Phildelphia, PA
    Posts
    1,146
    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++.
    FAQ

    "The computer programmer is a creator of universes for which he alone is responsible. Universes of virtually unlimited complexity can be created in the form of computer programs." -- Joseph Weizenbaum.

    "If you cannot grok the overall structure of a program while taking a shower, you are not ready to code it." -- Richard Pattis.

  5. #5
    Toaster Zach L.'s Avatar
    Join Date
    Aug 2001
    Posts
    2,686
    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.
    The word rap as it applies to music is the result of a peculiar phonological rule which has stripped the word of its initial voiceless velar stop.

  6. #6
    Registered User
    Join Date
    Dec 2003
    Posts
    7
    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)

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Finding a directory, and printing whats in it
    By booyah in forum C Programming
    Replies: 4
    Last Post: 11-12-2003, 10:52 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21