Question

For this computer assignment, you are to write and implement an interactive C++ program to find and print all prime numbers, which are less than or equal to a given value of n, using the algorithm known as the Sieve of Eratosthenes. A prime number p is an integer greater than 1 that is divisible only by 1 and p (itself). The algorithm begins by initializing a set container to contain all the integers in the range 2 to n. A loop makes multiple passes over the elements in the set, using successive integer key values 2, 3, 4, … Each pass “shakes free” nonprime numbers and lets them “filter through the sieve.” At the end, only the prime numbers remain. Begin with the integer m = 2, which is the smallest prime number. The pass scans the set and removes all multiples of 2, having the form 2 * k for k >= 2. The multiples cannot be prime numbers, because they are divisible by 2. At the end of the pass, we have removed all even numbers except 2. Next, look at the integer m = 3, which is a prime number. As with value 2, remove all multiples of 3, having the form 3 * k for k >= 3. The multiples 12, 18, and so forth, are even numbers, so they have already been removed from the set. The next key integer is m = 4, which is no longer in the set, because it was removed as a multiple of 2. The pass takes no action. The process continues until it removes all multiples of prime numbers. In other words, for integer m, remove all multiples of m, having the form m * k for k >= m.

The numbers that remain in the sieve are the prime numbers in the range 2 to n. The algorithm uses an optimization feature by looking at the key values for m <= sqrt ( n ). However, in your implementation, test all numbers m such that m * m <= n, rather than computing the square root of n.

Programming Notes:

1. Use a set container to store the prime numbers. In the STL, a set is implemented as an associative container, it uses the model of a mathematical set, it stores keys that are objects of a specified data type, where duplicate keys are not allowed. To use a set in your program, you need to insert the statement: #include in your header file.

2. In addition to the main ( ) routine, implement (at least) the following two subroutines in your program: • void sieve ( set < int >& s, int n ): This routine can be used to apply the Sieve of Eratosthenes algorithm to remove all nonprime numbers from the integer set s = { 2, 3, …, n }. • void print_primes ( const set < int >& s ): This routine can be used to print the elements in the integer set s (NO_ITEMS = 16 primes per line and ITEM_W = 4 spaces allocated for each prime). Sieve of Eratosthenes 2

3. The main ( ) routine creates an empty set of integers and prompts the user for an upper limit and calls the subroutine sieve ( ) to execute the Sieve of Eratosthenes. It calls the subroutine print_primes ( ) to print the prime numbers on stdout.

4. Include your header file prog3.h, by inserting the statement: #include “prog3.h” at the top of your source file prog3.cc.

ALSO PLEASE ATTACH AN HEADER FILE

Answer 1

Code:

untitled1.cpp

#include<iostream>
#include<set>
#include "untitled1.h"
using namespace std;
int main()
{
   int n;
   cout << "Enter n: " ;cin >> n;
   set < int > s;
   for(int i = 2;i < n;i++) s.insert(i);//inserting all numbers from 2 to n-1
   sieve(s, n);//calling sieve function
   print_primes(s);//
   return 0;
}
untitled1.h

#include<iostream>
#include<set>
void sieve( std::set < int >& s, int n)
{
   for(int i = 2; i * i <= n; i++)//iterate upto an element less than sqrt(n)
   {
       for(int j = 2; j * i < n;j++)//j*i stores all the multiples of i which are less than n
       {
           s.erase(j*i);//removing j*i from the set
       }
   }
}
void print_primes ( const std::set < int >& s )
{
   std::cout << "Prime numbers:" << std::endl;
   int cnt = 0;
   for( std::set < int > :: iterator it = s.begin(); it != s.end(); it++)
   {
       cnt++;
       std::cout << *it << " ";
       if(cnt == 16)
       {
           std::cout << std::endl;
           cnt = 0;
       }
   }
   std::cout << std::endl;
}

Output: