C++ assignment that im having issues with. please advise how to fix this. A prim

Question

C++ assignment that im having issues with. please advise how to fix this.

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.

#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]; <--- proble, here

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;
}

Explanation / Answer

#include <vector>
#include <boost/dynamic_bitset.hpp>
#include <cmath>
#include <limits>
#include <cmath>
#include <iostream>

boost::dynamic_bitset<> sieve_of_sundaram( std::size_t N )
{
const std::size_t M = N / 2 ;
boost::dynamic_bitset<> sieve(M) ;
sieve.flip() ;

for( std::size_t k = 1 ; k < M ; ++k )
{
const std::size_t L = (M-k) / ( 2*k + 1 ) ;
for( std::size_t j = k ; j <= L ; ++j ) sieve[ k + j + 2*k*j ] = false ;
}

return sieve ;
}

std::vector<int> prime_number_sequence( std::size_t lbound, std::size_t ubound )
{
auto sieve = sieve_of_sundaram(ubound) ;
std::vector<int> primes ;
if( lbound < 3 )
{
primes.push_back(2) ; lbound = 3 ;
}

for( std::size_t k = (lbound-1)/2 ; k < sieve.size() ; ++k )
if( sieve[k] ) primes.push_back( k*2 + 1 ) ;

return primes ;
}

int nth_prime_number( std::size_t n )
{
int number = 2 ;
if( n > 1 )
{
  
double ubound = std::max( 100.0, n * std::log(n) * 1.5 ) ;
assert( ubound < std::numeric_limits<std::size_t>::max() ) ;
auto sieve = sieve_of_sundaram(ubound) ;
std::size_t pos = 1 ;
for( std::size_t k = pos ; n > 1 ; ++k ) if( sieve[k] ) { pos = k ; --n ; }
assert( pos < std::numeric_limits<int>::max() / 2 ) ;
number = pos * 2 + 1 ;
}

return number ;
}

int main()
{
for( int n : prime_number_sequence( 7000, 7100 ) ) std::cout << n << ' ' ;
std::cout << ' ' ;

for( std::size_t n = 100 ; n < 1000000 ; n *= 10 )
std::cout << n+1 << ": " << nth_prime_number(n+1) << ' ' ;
}

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

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