Finding prime numbers program

[thatotherguy237]

Alright, I wanted to make a program that finds prime numbers and stores them in an array, being the newb I am, bugs everywhere and not much works the way it wants to.

  #include <iostream>
int Getelements(long *pointer_to_array)
{
    int numberofelements = 0;
    while(*pointer_to_array) //if pointer_to_array points to 0, break;
    {
        numberofelements++;
        pointer_to_array++;
    }
    return numberofelements;
}
int main()
{
    using namespace std;
    long list_of_primes[200] = {}; //set all of them equal to 0
    list_of_primes[0] = 2; //set the first prime number to 2


    //loop through lots of numbers
    for(int z = 3; z < 1000000; z++) //find primes between 3 and 1000000
    {
        int number_of_elements = Getelements(list_of_primes);
        for (int i = 0; i < number_of_elements; i++) //loop throught the list_of_primes array
        {
            if(z%list_of_primes[i] == 0) // if z is divisible by any of the numbers in the array, break
                break;
            else if(z%list_of_primes[i] != 0 && i == number_of_elements-1) //if z is not divisible AND it's the last loop, add z to the list of primes
                list_of_primes[i+1] = z;
        }
    }
    for(int x:list_of_primes) //prints primes
        cout << list_of_primes[x] << endl;
}

Ugly code, but not planning on any clean up until i actually get it to work.
Any suggestions?
Thanks in advance.
(Not sure if StackOverflow is a place for beginners so i posted the question here)

[ne555]

    for(int x:list_of_primes) //prints primes
        cout << x << endl;

> long list_of_primes[200] = {};
I think you are a little short

[thatotherguy237]

What do you mean by that?

[eyenrique]

@thatotherguy237 there are
more than 200 prime numbers
between 3-1000,000

the number of
prime numbers
under 1000 are: 168

so my example works
for the first 168 prime
numbers.

Number of prime numbers between 2-1000: 168

2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,
103,107,109,113,127,131,137,139,149,151,157,163,167,173,179,181,191,193,
197,199,211,223,227,229,233,239,241,251,257,263,269,271,277,281,283,293,307,
311,313,317,331,337,347,349,353,359,367,373,379,383,389,397,401,409,
419,421,431,433,439,443,449,457,461,463,467,479,487,491,499,503,509,521,
523,541,547,557,563,569,571,577,587,593,599,601,607,613,617,619,631,641,
643,647,653,659,661,673,677,683,691,701,709,719,727,733,739,743,751,757,
761,769,773,787,797,809,811,821,823,827,829,839,853,857,859,863,877,881,
883,887,907,911,919,929,937,941,947,953,967,971,977,983,991,997.

//PrimeNumbers.cpp
//##

#include <iostream>
using std::cout;
using std::endl;

bool isPrime(int number);

int main(){

        int index=0;
        int const SIZE=168;
        int number_of_primes=0;
        int container_of_primes[SIZE];
        

        //find and store prime numbers between 2-1000  
        for(int number=2;number<=1000;number++){
                if(isPrime(number)){
                        container_of_primes[index]=number;      
                        index++;
                        number_of_primes++;
                }//end if
        }//end for

        cout<<"Number of prime numbers between 2-1000: "<<number_of_primes<<'\n'<<endl;

        //prints array content -container_of_primes-
        for(int i=0;i<SIZE;i++){
                cout<<container_of_primes[i]<<((i+1)!=SIZE?',':'.');
        }//end for
        cout<<endl;
        


return 0; //indicates success
}//end of main

bool isPrime(int number){

        for(int i=2;i<number;i++){
                if(number%i==0) return false;
        }//end for

return true;
}//end function isPrime 

[Chervil]

One suggestion, the function Getelements() seems an inefficient way to keep track of how many elements of the array are in use. It would be simpler to use an ordinary integer variable, give it an initial value of 1 because the array contains the prime number '2' as the first element. Then simply increment the count each time you add a new element. (Much better would be to use a vector instead of a plain array).

[long double main]

There are 78498 primes less than 1 million.

Somehow, I get the feeling that you just picked an arbitrary upper bound, and you just wanted to loop until you found 200 of them.

In that case...

First off, if you're going to use a Getelements function to count array elements, you should probably first initialize all of the elements of your array to zero. (Otherwise, there's no guarantee that the element past the last prime you found is a zero.)
A better (more efficient) solution would be to simply keep track of that number yourself (all you need to do is increment that number when you add a new prime).
In fact, you can just use your number_of_elements variable for that purpose:

#include <iostream>

// No need for any Getelements function

int main()
{
    using namespace std;
    long list_of_primes[200] = {}; //set all of them equal to 0
    list_of_primes[0] = 2; //set the first prime number to 2
    int number_of_elements = 1; // Starting out with 1 prime (2)
    

Now, for your for loop, since there are way more than 200 primes between 3 and 1000000, you can actually just loop until number_of_elements == 200. Also, since you know right off the bat that no even number (other than 2, which you've already taken care of) is prime, you can increment by 2 instead of just 1:

for (long z = 3; number_of_elements < 200; z += 2)
{

Also note that since your array is declared as long list_of_primes[200], you might as well just be consistent and declare z as a long as well.

Now, in your code right now:

for (int i = 0; i < number_of_elements; i++) //loop throught the list_of_primes array
{
    if(z%list_of_primes[i] == 0) // if z is divisible by any of the numbers in the array, break
        break;
    else if(z%list_of_primes[i] != 0 && i == number_of_elements-1) //if z is not divisible AND it's the last loop, add z to the list of primes
        list_of_primes[i+1] = z;
}

On line 27, since you've already checked on line 25 if z%list_of_primes[i] == 0, you know that if your program reaches this point, z cannot possibly be divisible by list_of_primes[i], so you don't need to check that again:

for (int i = 0; i < number_of_elements; i++)
{
    if (z % list_of_primes[i] == 0) // If z is divisible by anything, break
        break;
    else if (i == number_of_elements - 1) // Otherwise, we know it's not divisible, so just check if we've hit the end yet
    {

Now, since we got rid of our Getelements function, we'll need to keep track of the array size ourselves. All that really requires is to increment the value of number_of_elements each time you add a new prime to the array:

list_of_primes[i+1] = z;
++number_of_elements;
// Optionally add a break; here (if you don't, it'll go an extra iteration, but that's okay) 

Finally, when printing the elements:

for(int x:list_of_primes) //prints primes
    cout << x << endl; // Not list_of_primes[x] 

Since x takes on the values of each of the elements of list_of_primes, not the indices of those values, you should simply print the value of x rather than list_of_primes[x] (which will make your program go way out of bounds O_o).

If all goes well, the last number to be printed should be 1223.

Also note that this is all much easier to do using std::vector -- you won't have to manually keep track of the size, and plus, you can easily extend the size to just about as large as you could ever want (memory permitting).

[thatotherguy237]

Thanks, Long Double Main!
Not only did you point out the flaws, you also optimized it! :D

In all honesty, this kind of stuff happens way more often than it should. I get working on a tiny project, get the general idea of how it's going to work, and the code gives up on me.

Sigh...

Anyways, this program was actually a subprogram that's part of a bigger one, from the challenge on http://projecteuler.net/problems

Thank you once again!

[pukol]

Hello.. Try looking at my "Find the primes codes" at http://www.cplusplus.com/forum/beginner/122090/

If you want to find more than 200 primes then i suggest looking at it and maybe it can help you..