C++ assignment A prime number is an integer greater than 1 and divisible only by

Question

C++ assignment

A prime number is an integer greater than 1 and divisible only by itself and 1. An integer x is divisible by an integer y if there is another integer z such x = y* z. The Greek mathematician Erathosthenes (pronounced Er- ah - tos- thin- eeze) gave an algorithm for finding all prime numbers less than some integer N. This algorithm is called the Sieve of Erathosthenes.

The algorithm works like this: Begin with a list of integers 2 through N. The number 2 is the first prime. (It is instructive to consider why this is true.) The multiples of 2— that is, 4, 6, 8, etc. — are not prime. We cross these off the list. Then the first number after 2 that was not crossed off, which is 3, is the next prime. The multiples of 3 are not primes. Cross these off the list. Note that 6 is already gone, cross off 9, 12 is already gone, cross off 15, etc. The first number not crossed off is the next prime. The algorithm continues on this fashion until we reach N. All the numbers not crossed off the list are primes.

Write a program using this algorithm to find all primes less than a user- supplied number N. Use a vector container for the integers . Use an array of bool initially set to all true to keep track of crossed off integers. Change the entry to false for integers that are crossed off the list.

Display the prime numbers using the Erathosthenes algorithm. Any other algorithm will not be accepted and the submission will receive zero.

The program should not allow the user to enter negative number. Write an exception hander for this task. The program should print an error message and keep asking the same question until the user enters a positive number.

Explanation / Answer

#include <iostream>
#include<cstring>
using namespace std;
void findPrimes(int n);
int main()
{
int n;
try{
cout<<"enter N value ";
cin>>n;
if(n<=0)
throw "enter a positive number";
findPrimes(n);
}
catch (const char* msg) {
cerr << msg << endl;
}
return 0;
}
void findPrimes(int n)
{
bool a[n+1];
int i,j;
for(i=0;i<+n;i++)
{
a[i]=1;
}
for(i=2;i<=n;i++)
{
if(a[i]==1) // check weather i is prime or not
{
for(j=2;j*i<=n;j++)
{
a[i*j] = 0; //mark all the multiples of that prime number as not prime
}
}
}
for(i=2;i<=n;i++)
{
if(a[i]==1)
cout<<i<<" ";
}
cout<<endl;
}

input:

enter N value

50

output:

input:

enter N value

-1

enter a positive number

another version using vector

#include <iostream>
#include<cstring>
#include<vector>
using namespace std;
void findPrimes(vector<int> p, int n);
void displayPrimes(vector<int> p);
int main()
{
int n;
vector<int> p;

try{
       cout<<"enter N value ";
       cin>>n;
   if(n<=0)
   throw "enter a positive number";

       findPrimes(p,n);
  
   }

   catch (const char* msg) {
   cerr << msg << endl;
   }
return 0;
}

void findPrimes(vector<int> p, int n)
{
bool a[n+1];
int i,j;
   for(i=0;i<+n;i++)
   {
       a[i]=true;
   }

   for(i=2;i<=n;i++)
   {
       if(a[i]==true) // check weather i is prime or not
       {
p.push_back(i);
           for(j=2;j*i<=n;j++)
           {
if(a[i*j]==true)//check whther i*j is already striked off
           a[i*j] = false; //mark all the multiples of that prime number as not prime
           }
       }
   }
displayPrimes(p);
}
void displayPrimes(vector<int> p)
{
cout<<p.size()<<endl;
for(int i=0;i<p.size();i++)
cout<<p[i]<<endl;
}

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

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