The following code supposedly implements the Sieve of Eratos

The following code supposedly implements the Sieve of Eratostenes.

Read the following instructions carefully and doucment everything in comments // .

i. Make it work in your environment

ii. Modify it so that you can time the code involved in finding the prime numbers excluding the time used for I/O. This may require increasing the value of N.

iii. Modify the display of the results so that each line only contains 10 numbers

iv. Display the number of prime numbers found in each run.

v. Change the array type from int to char and comment on changes to run time.

Vi. Change the array type to bool and comment on changes to run time.

#include <iostream.h>

static const int N = 1000;

int main()

{ int i, a[N];

    for (i = 2; i < N; i++) a[i] = 1;

    for (i = 2; i < N; i++)

      if (a[i])

        for (int j = i; j*i < N; j++) a[i*j] = 0;

    for (i = 2; i < N; i++)

      if (a[i]) cout << \" \" << i;

    cout << endl;

}

B. Change the static array in part A to a dynamic array and compare the run times to the variations you tried in part A.

     Be sure to use types char and bool in your testing.

C. Change the static array in part A to a vector and compare the run times to the variations you tried in part A.

     Be sure to use types char and bool in your testing.

Solution

A) Solution:

#include <iostream.h>
//intialize the static element
static const int N = 1000;
int main()
{
//variable declation
int i, a[N];
//loop initialization and assign value 1 to all array elements
for (i = 2; i < N; i++) a[i] = 1;
//loop repeats N times and checking for prime nuber
for (i = 2; i < N; i++)
if (a[i])
   for (int j = i; j*i < N; j++) a[i*j] = 0; //checks for prime number
for (i = 2; i < N; i++) //printing prime numbers
if (a[i]) cout << \"\\t\" << i; //\"\\t\" for tab which is used to print 10 number only per a row
cout << endl;
return 0;
}

change array as Character type:

#include <iostream.h>
//intialize the static element
static const int N = 127;//here the character range is to be set as 127
int main()
{
//variable declation
char i, a[N];
//loop initialization and assign value 1 to all array elements
for (i = 2; i < N; i++) a[i] = 1;
//loop repeats N times and checking for prime nuber
for (i = 2; i < N; i++)
if (a[i])
   for (int j = i; j*i < N; j++) a[i*j] = 0; //checks for prime number
for (i = 2; i < N; i++) //printing prime numbers
if (a[i]) cout << \"\\t\" << i; //\"\\t\" for tab which is used to print 10 number only per a row
cout << endl;
return 0;
}

Boolean:

#include <iostream.h>
//intialize the static element
static const int N = 2;//here the boolean range is to be set as 2
int main()
{
//variable declation
char i, a[N];
//loop initialization and assign value 1 to all array elements
for (i = 2; i < N; i++) a[i] = 1;
//loop repeats N times and checking for prime nuber
for (i = 2; i < N; i++)
if (a[i])
   for (int j = i; j*i < N; j++) a[i*j] = 0; //checks for prime number
for (i = 2; i < N; i++) //printing prime numbers
if (a[i]) cout << \"\\t\" << i; //\"\\t\" for tab which is used to print 10 number only per a row
cout << endl;
return 0;
}

//but here we can not execute with boolean type it shows somany errors.

B) Dynamic Array:

#include <iostream.h>
//intialize the static element

static const int N=1000;
int main()
{
//variable declation
int i;
//here we are declaring a dynamic array and intialize with new
int *a=new int[N];
for (i = 2; i < N; i++)
{
a[i] = 1;
}
//loop repeats N times and checking for prime nuber
for (i = 2; i < N; i++)
if (a[i])
   for (int j = i; j*i < N; j++) a[i*j] = 0; //checks for prime number
for (i = 2; i < N; i++) //printing prime numbers
if (a[i]) cout << \"\\t\" << i; //\"\\t\" for tab which is used to print 10 number only per a row
cout << endl;

delete [] a; //delete the elements of dynamic array
return 0;
}

charcter type:

#include <iostream.h>
//intialize the static element

static const int N=127;
int main()
{
//variable declation
int i;
//loop initialization and assign value 1 to all array elements
char *a=new char[N];
for (i = 2; i < N; i++)
{
a[i] = 1;
}
//loop repeats N times and checking for prime nuber
for (i = 2; i < N; i++)
if (a[i])
   for (int j = i; j*i < N; j++) a[i*j] = 0; //checks for prime number
for (i = 2; i < N; i++) //printing prime numbers
if (a[i]) cout << \"\\t\" << i; //\"\\t\" for tab which is used to print 10 number only per a row
cout << endl;
delete []a;
return 0;
}

Vectors:

#include <iostream.h>
//intialize the static element

static const int N=1000;
int main()
{
//variable declation
int i;
//loop initialization and assign value 1 to all array elements
vector <int> a(N,0);
for (i = 2; i < N; i++)
{
a[i] = 1;
}
//loop repeats N times and checking for prime nuber
for (i = 2; i < N; i++)
if (a[i])
   for (int j = i; j*i < N; j++) a[i*j] = 0; //checks for prime number
for (i = 2; i < N; i++) //printing prime numbers
if (a[i]) cout << \"\\t\" << i; //\"\\t\" for tab which is used to print 10 number only per a row
cout << endl;
return 0;
}

character type:

#include <iostream.h>
//intialize the static element

static const int N=127;
int main()
{
//variable declation
int i;
//loop initialization and assign value 1 to all array elements
vector <char> a(N,0);
for (i = 2; i < N; i++)
{
a[i] = 1;
}
//loop repeats N times and checking for prime nuber
for (i = 2; i < N; i++)
if (a[i])
   for (int j = i; j*i < N; j++) a[i*j] = 0; //checks for prime number
for (i = 2; i < N; i++) //printing prime numbers
if (a[i]) cout << \"\\t\" << i; //\"\\t\" for tab which is used to print 10 number only per a row
cout << endl;
return 0;
}