/*Sieve of Eratosthenes
1.Write a list of numbers from 2 to the largest number you want to test for primality.
Call this List A. (This is the list of squares on the left-hand-side of the picture.)
2.Write the number 2, the first prime number, in another list for primes found.
Call this List B. (This is the list on the right-hand-side of the picture.)
3.Strike off 2 and all multiples of 2 from List A.
4.The first remaining number in the list is a prime number.
Write this number into List B.
5.Strike off this number and all multiples of this number from List A.
The crossing-off of multiples can be started at the square of the number, as lower multiples have already been crossed out in previous steps.
6.Repeat steps 4 and 5 until no more numbers are left in List A.
*/
#include
#include
using namespace std;
const int SIZE = 1000;
int main ()
{
int arr[SIZE];
int i;
for ( i= 0 ; i < SIZE; i ++ )
{
arr [i] = 1;
}
int p = 2; //first prime number
while ( p*p < SIZE)
{
for ( i=2 ; i*p < SIZE; i++ )
{
arr[p*i] = 0;
//cout << p*i << endl;
}
for ( i= p ; i < SIZE; i ++ )
{// find prime
if (arr[i] == 1 && i > p) // find the next prime number
{
p = i;
//cout << i << endl;
break;
}
}
}
int line=0;
for ( i= 2 ; i < SIZE; i ++ )
{
if(arr [i] == 1)
{
line ++;
cout << setw (4)< if (line % 10 == 0)
cout << endl;
}
}
cout << endl;
return 0;
}
