Calculating Prime Numbers

[killingthemonkey]

I am trying to calculate all the prime numbers up to a number entered by the user. The algorithm is laid out for me. I'm using 'Erasthones Sieve'. It's laid out in the comment at the beginning of the code. Instead of outputting just the primes it prints all of the numbers. Where is my logic error?

Here is my code:

/*
1. Create a contiguous list of numbers from two to some highest number n.
2. Strike out from the list all multiples of two (4, 6, 8 etc.).
3. The list's next number that has not been struck out is a prime number.
4. Strike out from the list all multiples of the number you identified in the previous step.
5. Repeat steps 3 and 4 until you reach a number that is greater than the square root of n (the highest number in the list).
6. All the remaining numbers in the list are prime.*/

#include <iostream>
using namespace std;

int main()

{
    int i;
    int x;
    int upperRange;
    int * testArray;
    int incrementingTest = 2;
        
    cout << "Please enter a number: ";
    cin >> upperRange;
    
    testArray = new int [upperRange];
    
    //Populate array
    for (i = 1; i <= upperRange; i++)
    {
        testArray[i] = i;
    }

    
    cout << "-----------------------------------" << endl;
    cout << endl;
    
    //Loop to test for prime
    for (x = 1; x <= upperRange; x++)
    {
        for (i = 1; i <= upperRange; i++)
        {
            if (testArray[i] % incrementingTest == 0)
            {
               testArray[i] = 0;
            }
        incrementingTest++;
            
        }
    }
    
    //Loop to display results
    for (i = 1; i <= upperRange; i++)
    {
        if (testArray[i] != 0)
        {
           cout << testArray[i] << endl;
        }
        
    }
    return 0;
    
}

If I put incrementingTest++ inside the if statement then all I get for out put is 1.

[firedraco]

Well, you do know you aren't follow the logic they gave you...anyway, why do you even have a for loop for x...it doesn't affect anything.

As for why it prints out all of the numbers...it's because you are incrementing your test value in the wrong place, when 'i' is 1, your incrementer is 2, but then when 'i' is 2, you incrementer is 3, because you added 1.

[seymore15074]

Also note that you create an array on line 24 and then proceed to access the array with the size as an index in your for loops. That will write one element past the end of your array.

[killingthemonkey]

firedraco,
The internal for cycles through the array once with incrementingTest at a single value. When it finishes its cycle, the external loop increments incrementingTest and sends it through the internal loop again.

seymore15074,
The <= stops the loop from going beyond the end of the array.

[Duthomhas]

I think it interesting when someone asks for advice, then promptly dismisses all the advice given.

Perhaps you ought to reconsider...

[killingthemonkey]

Duoas,
I am not dismissing the advice. I am explaining exactly what I am doing. My test integer has to be incremented after going all the way through the array. So, the nested loop is necessary.

As for using the size for my index, am I wrong? Doesn't the <= stop the loop at the end of the array?

If they're right, tell me so, and show me how.

[helios]

Well, here's the problem. You seem to be confused about arrays.
An array declared as array[10] has elements {0,1,2,3,4,5,6,7,8,9}, therefore, you need to loop through it with
for (int a=0;a<10;a++);
not
for (int a=1;a<=10;a++);

As for the x loop, I think I see what you're trying to do. You're doing a primality check on the range [1;upperRange]. There's really no need to store the results in an array. Just print them directly.
The for i is incorrect. It should start on 2 and end on testArray[i]:
for (i = 2; i < testArray[i]; i++);
or
for (i = 2; i < x; i++);
The test should be
if (testArray[i] % i == 0);
or
if (x % i == 0);

[Duthomhas]

> I am not dismissing the advice. I am explaining exactly what I am doing.

You assume too much. We already know what you are trying to do, and how... but you are failing for the exact reasons that firedraco (and now helios) have given. Not because we misunderstand you or your code. Justifying yourself against the advice given you is dismissive, and a bit brash.

Though I am glad you appear to be thinking about the problem.

Helios The Sieve of Eratosthenes works by crossing-off numbers (which must be stored somehow --an array works nicely). The Wikipedia has a nice animation http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes
(The instructions given by the professor were taken directly from the article.)

Helios is correct in that once you identify a prime, you can print it immediately --there is no need to have a separate display loop. But that doesn't really matter either way. (Your assignment was not specific about if and when you are supposed to print the primes, but the way you have it works best if you are to stop looping at sqrt(n).)

Firedraco said it correctly: you are not following the algorithm given you. You need to rethink the loops, and some variable names. Here are some hints:

1. Useful variable names:

int highestNumber;              // user's input == size of array minus one
int squareRootOfHighestNumber;  // when to stop the outer loop (see note below)
int currentPrime;               // outer loop counter
int multipeOfCurrentPrime;      // inner loop (mega-hint: Wow your professor!) 

I give these names to help you think a little more clearly about the algorithm. For example, highestNumber is better than upperRange because it is more explicit, doesn't mix terminologies, and doesn't imply the wrong thing for the array size.

2. Use one outer loop and two inner loops. Steps 3 and 4 are each an inner loop (step 2 is actually the same as step 4 --the difference is just that 2 is the very first prime; you don't need a step 3 to find it). Step 5 is the outer loop.

3. Notes: you don't actually have to calculate the square root of the highest number. If your currentPrime² > highestNumber then you are done. Either method will do. (I would use the extra variable --just because I'm an optimization freak-- instead of doing an extra multiplication each time through the loop's test.)

Hmm, I think that should have answered your question... (I actually started this early this morning --then took a six-hour break to watch my niece --and only now did I finish... Some lossage may have occurred.) :-P

Good luck.