What is the significance of this C++ code and what does it do?

[sandy.bridge]

Hey guys. I just want to see if I am indeed "seeing" the significance of the code that is to follow. I will follow it with a brief explanation of what I thought the code did. Thanks in advance.

	const int N = 15;    
	bool table[N];

	int i = 0;
	while (i < N)
	{
		table[i] = true;
		i = i + 1;
	}

	table[0] = false;
	i = 2;
	while (i < N)
	{
		if (table[i])
		{
			int j = 2*i;

			while (j < N)
			{
				table[j] = false;
				j = j + i;
			}
		}
		i = i + 1;
	}

	i = 0;
	while (i < N)
	{
		if (table[i])
		{
			cout << i << " ";
		}
		i = i + 1;
	}
	cout << endl;

This program scans through the program in accordance to properties exhibited by the integer value i. If the element in the array had a property being tracked, then it was assigned Boolean true. If it was not, then it was assigned Boolean false. This program demonstrates how one can scan through an array, pursuing a particular property, and henceforth convey which elements within that array had that property.

 

[D H]

You're missing the forest for the trees. This is a simple algorithm to find the prime numbers. It's called the sieve of Eratosthenes.

 

[sandy.bridge]

That is the end result; but are any details in my explanation off?

 

[d3mm]

Well you have not explained what it does. It makes a table of numbers. It marks multiples of 2, then multiples of 3, then multiples of 4, then multiples of 5, etc. Eventually only prime numbers remain.

 

[LudusRex]

I can see that this code is attempting to implement the Sieve of Eratosthenes algorithm, which is used to find all prime numbers up to a given number. The code is using a boolean array to track which numbers are prime and which are not. The first while loop is setting all values in the array to true, indicating that all numbers are initially considered prime. Then, the second while loop is starting at the number 2 and checking if it is marked as prime in the array. If it is, then all multiples of 2 are marked as not prime in the array. This process is repeated for all numbers up to N, resulting in an array where all non-prime numbers are marked as false. Finally, the last while loop is printing out all the numbers that are still marked as true, indicating that they are prime numbers. Overall, this code is a clever and efficient way of finding prime numbers within a given range.