The Sieve of Eratosthenes to find prime numbers, stuck in an infinite loop

[bdavis21]

My problem here is that when I try to find all the multiples of two and zero them out I get stuck in an infinite loop of 2, I am unsure how to find multiples of two without using modulus or division which I am not allowed to do. If you can help me figure out why I am getting stuck in an infinite loop of 2's that would be very helpful, thanks. Also since this is my first time using this forum I do not know how to put my code in a block(or whatever the name is).

#include <iostream>
#include <cmath>
#include <string>
using namespace std;

void sieve(int array[], int num); // have to use this function

int main(void){
	const int maxNum = 101;
	int prime[maxNum];
	sieve(prime, maxNum);

	system("pause");
	return 0;
}

void sieve(int array[], int num){

	if (num >= 2){
		for (int i = 2; i < num; i++){
			array[i] = i; // created an array of all my numbers 
			for (int j = 2; j < num; j = i + 2){

				i = false; // trying to zero the numbers that are a multiple of 2
				cout << i << ", ";
			}



			//cout << i << ", ";
		}
	}
	return;
}

[TarikNeaj]

Hey. Code tags work like this - http://www.cplusplus.com/articles/jEywvCM9/

You're being stuck in an infinite loop beeecaaaaaaauseeeeeeeeeeeeeeeeeeeeeeeee

i never increases, even if you do for (int i = 2; i < num; i++) becauseeeeeeeeeeeeeeeeeeeeeeeeeeeeee

i = false; You keep resetting i to be equal to 0 so it never reaches its destination, or even comes close to it.

[bdavis21]

Thanks for replying so fast, I code tags to make it easier on the eyes.

For j = i + 2 I am trying to include every multiple of 2 and since I cannot divide or
use modulus I tried to use every number that 2 can add up to. For i = false I was
trying to set every multiple of 2 to zero.

[bdavis21]

What I am trying to ask and figure out is how would I create a loop that would turn every multiple of 2 to zero.

[kbw]

every multiple of 2

What do you mean?

[TarikNeaj]

@kbw

I googled it, and apparently it means.

2 · 0 = 0	2 · 1 = 2    	 2 · 2 = 4  	2 · 3 = 6	2 · 4 = 8
2 · 5 = 10	2 · 6 = 12 	 2 · 7 = 14    2 · 8 = 16      2 · 9 = 18

So basically, every even number ever. Something modulus Would be fantastic for, but he cant use it because his professor is a smart beautiful man/woman.

[bdavis21]

LOL @TarikNeaj yes this is my problem. That is why I tried to make a loop that would count everyone of those multiples and take them out. Here is what The Sieve of Eratosthenes is:

Make a list of all the integers less than or equal to n (and greater than one). Strike out the multiples of all primes less than or equal to the square root of n, then the numbers that are left are the primes.

For example, to find all the primes less than or equal to 30, first list the numbers from 2 to 30.

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

The first number 2 is prime, so keep it (we will color it green) and cross out its multiples (we will color them red), so the red numbers are not prime.

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

The first number left (still black) is 3, so it is the first odd prime. Keep it and cross out all of its multiples. We know that all multiples less than 9 (i.e. 6) will already have been crossed out, so we can start crossing out at 32=9.

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

[TarikNeaj]

I mean, Here is what Im stuck on. Do you haaaave to turn it into 0, or is it okay to just print out 0 in the place of the 2,4,6,8 etc? So you would print out

1 0 3 0 5 0 7 0 etc

[bdavis21]

i need to keep the number 2 because it is prime and I have to turn the other multiples of 2 into 0.
ex: prime number from 1-10

2, 3, 5, 7

[kbw]

const int max = 10;
for (int i = 2; i <= max; i = (i == 2) ? 3 : (i + 2))
{
    // your code
}

[Horscht]

You are basically moving through your array from beginning to end want to zero out all of the current indexes multiples, right?
So at i = 5, you want to cross out 10, 15, 20 etc, starting at the NEXT multiple, so in this case 10.
So you start at 2*i and go in steps of i.
Look at your inner loop for j and think about this.
Tip: You can skip one iteration by using the keyword continue, like this:

for(int i = 0; i < 6; i++)
{
  if(i == 3)
  {
    continue;
  }
  cout << i << ", ";
}
// Output: 0, 1, 2, 4, 5,  

You can use this to check if you have already zeroed out the current array[i], and skip to the next iteration, otherwise your second loop would go in steps of 0 and give you an infinite loop.
I found a solution but since it's your homework you should be the one to figure it out ;)
For my solution I filled the array first with all the numbers starting at index 2, since otherwise it would be hard to distinguish between values that you have already set to 0 or were initialized to 0 in the first place. (At least thats what I think).
Hopefully I didn't give you too much information and ruin the exercise for you.

[bdavis21]

Thanks for replying, kbw can you explain to me what you code is doing? I ran it and I know what it did but I do not know what the question mark and colon mean. Also Horscht you have the right idea of what I am trying to do, I want to start at 2 and cross out all the multiples, then move to 3, then move to 5 and so on. My actual assignment wants me to find all the primes from 0 to 1000000 so if I tried to check number by number my code would take hours. thanks tho.

[bdavis21]

I just found out I can use any math excluding division or modulus meaning I can use multiplication.

[fg109]

http://www.cplusplus.com/forum/beginner/159321/

I'm sure someone else can come up with a better way, but hey, it works.