7.27 A prime integer is any integer that is evenly divisible only by itself and

Question

7.27

A prime integer is any integer that is evenly divisible only by
itself and 1. The Sieve of Eratosthenes is a method of finding prime numbers. It operates as follows:
a) Create an array with all elements initialized to 1 (true). Array elements with prime subscripts
will remain 1. All other array elements will eventually be set to zero. You’ll ignore
elements 0 and 1 in this exercise.
b) Starting with array subscript 2, every time an array element is found whose value is 1,
loop through the remainder of the array and set to zero every element whose subscript
is a multiple of the subscript for the element with value 1. For array subscript 2, all elements
beyond 2 in the array that are multiples of 2 will be set to zero (subscripts 4, 6,
8, 10, etc.); for array subscript 3, all elements beyond 3 in the array that are multiples
of 3 will be set to zero (subscripts 6, 9, 12, 15, etc.); and so on.
When this process is complete, the array elements that are still set to one indicate that the subscript
is a prime number. These subscripts can then be printed. Write a program that uses an array of
1000 elements to determine and print the prime numbers between 2 and 999. Ignore element 0 of
the array.

Explanation / Answer

PROGRAM:

OUTPUT:

CODE TO COPY:

#include <iostream>
using namespace std;
void prime(int a[1000]);
int a[1000];
int main()
{
    a[0] = 0;
   a[1] = 0;

//initialing array elements to 1(true)
for (int i = 2; i < 1000; i++)
{
     a[i] = 1;
}
prime(a);

//printing prime numbers between 2 and 999
cout<<"Primes numbers between 2 and 999";
for (int i = 0; i <1000; i++)
{
      if (a[i] == 1)
      {
         cout << i<<" ";
   }
}

system("PAUSE");
return 0;
}

//code to find prime numbers using Sieve of Eratosthenes method
void prime(int a[1000])
{
     for (int i = 2; i < 1000/2; i++)
    {
           if (a[i] == 1)
          {
                 for (int j = i*2; j < 1000; j+=i)
               {   
                     a[j] = 0;
                }
          }
    }
}

Related Questions

Navigate

• Browse (All)
• Browse 7
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.