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