C++

Forum

 
Prime number finder not looping correctly

suchanoob (14)
I made a program where the user inputs a number and all prime numbers up to and including it are displayed. My algorithm involves starting at 2 and deleting all multiples of it except itself, then 3 and so on. This code erases all multiples of 2 just fine but for some reason will not pass numbers any higher. It's pretty much ignoring the z++ in my for loop. What am I doing wrong?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
 
#include <iostream>
#include <set>
using namespace std;

int main()
{
    set<int>s;
    int n,x,y,z;
    cout<<"Number: ";
    cin>>n;
    y=2;
    for(x=0;x<n-1;x++)
    {
        s.insert(y);
        y++;
    }
    set<int>::iterator cnt;
    for(z=2;z<n;z++)
    {
        cnt=s.find(z+1);
        while(cnt!=s.end())
        {
            if(*cnt%z==0)
            s.erase(cnt++);
            else
            ++cnt;
        }
    }
    for(cnt=s.begin();cnt!=s.end();cnt++)
    cout<<*cnt<<"\n";
    system("pause");
    return 0;
}
histrungalot (272)
You are not entering the while loop all of the time.
For example:
1. z = 2
2. find z+1 = 3
3. you find if and remove all of the multiples of 2
4. Now, z = 3
5. find z+1 = 4
6. you don't find 4 because it is a multiple of 2 and it was removed.

The same thing happens for 5, 7, 11 because +1 is a even number that you have removed on the first iteration of the for loop.

You need to change the logic on how you iterate thru the set.
If you change line 20 to cnt=s.find(z); and add an extra check on line 23 it will work.
Topic archived. No new replies allowed.