**Topic :**Riddle of Eratosten

**Author :**Ilia Yordanov

**Page :**

**1**

This is very simple, but in the same time, extreamely fast algorithm for finding prime numbers (numbers that can divide only by 1 and

by number, itself - 2,3,5,7,11,13,17...)

**1. Explaining the algorithm**

Let N is the number, to which, we have to find all prime numbers. For example, if N =10, the prime numbers would be:

2,3,5 and 7

So, we make an array with N-1 elements. The first cell (0) is filled with 2, and every next, is increased by one. So the array would look like that:

*2 ; 3 ; 4 ; 5 ; 6 ; 7 ; 8 ; 9 ; 10*

Now, the algorithm states:

1) We get the first element- 2

Now, we go through the whole loop, and delete all the elements that are dividable by 2. Thiw would mean, to delete 4,6,8 and 10. As we can't delete them from the array, I suggest you just to replace them with 0 (NULL).

2) We now get the next element - 3

And we do the same procedure- we delete all elements that are dividable by 3. This would mean to delete 9 (6 has already been deleted)

3) Now, we see that the next element is 0 (it should be 4, but we deleted it (replaced it with 0), so it is zero). So, as it is 0, we skip it, and go to the next one- 5. And repleat the same procedure. In this case, we will not delete any elements, as the only number dividable by 5 from those we have (to 10), is the 10. But we deleted the 10 already, so it is 0.

That's the algorithm.

I hope you got it!

If not, feel free to see the code that demonstrates it:

**2. Code example**

#include <iostream.h>

void main()

{

int n;

int i,k; //for the loops

cout << "n= ";

cin >> n;

n--; //we decrease by 1, because "1"

//(the digit 1) is not used in the array

int *arr = new int[n]; //create the array

//fill the array

for(i=0;i<n;i++)

arr[i] = i+2;

for(i=0;i<n;i++) //go through the loop

{

if(arr[i] != 0) //if the current element has not been deleted

{

for(k=i+1;k<n;k++)

{

if(arr[k] != 0)

{

if(arr[k]%arr[i] == 0)

arr[k] = 0;

}

}

}

}

//show the prime numbers

for(i=0;i<n;i++)

if(arr[i] != 0)

cout << arr[i] << " ; ";

cout << endl;

}

If you have any questions, feel free to contact me at:

*loobian@cpp-home.com*

This article is copyrighted to cpp-home.com and loobian, and can't be republished without permission from the author!

**Page :**

**1**