Programming C++ Exercise 5.2.1. Optimize the prime-number function by calculatin

Question

Programming C++

Exercise 5.2.1. Optimize the prime-number function by calculating the square root of n only once during each function call. Declare a local variable sqrt_of_n of type double. (Hint: A variable is local if it is declared inside the function.) Then use this variable in the loop condition.

Exercise 5.2.2. Rewrite main so that it tests all the numbers from 2 to 20 and prints out the results, each on a separate line. (Hint: Use a for loop, with i running from 2 to 20.)

Exercise 5.2.3. Write a program that finds the first prime number greater than 1 billion (1,000,000,000).

Exercise 5.2.4. Write a program that lets the user enter any number n and then finds the first prime number larger than n.

Explanation / Answer

// C++ code
#include <iostream>
#include <math.h>
using namespace std;

// Exercise 5.2.1
bool isPrime(long long int n)
{
   long double sqrt_of_n = sqrt(n);

   if(n == 2)
       return true;

   if(n%2 == 0)
       return false;

   for (long long int i = 2; i <= sqrt_of_n; ++i)
   {
       if(n%i == 0)
           return false;
   }

   return true;
}

int main()
{
   // Exercise 5.2.2
   cout << "Prime numbers between 2 and 20: ";
   for (int i = 2; i <= 20; ++i)
   {
       if(isPrime(i) == true)
       {
           cout << i << " is prime ";
       }
   }

   // Exercise 5.2.3
   int t = 1000000000;
   while(true)
   {
       if(isPrime(t) == true)
           break;
       t++;
   }

   cout << " First prime number greater than 1000000000: " << t << endl;

   // Exercise 5.2.4
   long long int n;
   cout << " Enter n: ";
   cin >> n;

   t = n+1;
   while(true)
   {
       if(isPrime(t) == true)
           break;
       t++;
   }

   cout << "First prime number greater than " << n << " is " << t << endl;

  return 0;
}

/*
output:

Prime numbers between 2 and 20:
2 is prime
3 is prime
5 is prime
7 is prime
11 is prime
13 is prime
17 is prime
19 is prime

First prime number greater than 1000000000: 1000000007

Enter n: 10289393
First prime number greater than 10289393 is 10289407

*/

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

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