Programming C++ Exercise 4.2 Example 4.2.1. Revise Example 4.2 to make it more o

Question

Programming C++

Exercise 4.2

Example 4.2.1. Revise Example 4.2 to make it more optimal. When you consider the speed of today’s microprocessors, it’s unlikely you’ll see a difference in execution, although if you attempt to test an extremely large number, say, more than a billion, you might see a difference. (By the way, good luck in finding a prime number in that range, if you’re just looking for one by chance. Prime numbers become rarer as you get into larger values.) In any case, the following changes to code make the program more efficient for large numbers: Calculate the square root of n only once by declaring a variable square_root_of_n and determining its value before entering the for loop. This variable should be a double variable. Once a divisor of n is found, you don’t need to look for any more divisors. Therefore, in the if statement inside the loop, add a break statement (breaking out of the loop) after setting is_prime to false.

Explanation / Answer

Here is the modified/improved version for your code:

#include <iostream>
#include <cmath>

using namespace std;

int main()
{
    int n = 0;   //Number to test for prime-ness
    bool is_prime = true;   //Boolean flag; assume true until proven otherwise.
   
    //Get a number from the keyboard.
   
    cout << "Enter a number and press ENTER: ";
    cin >> n;
   
    //Calculate the square root of n only once by declaring a variable
    //square_root_of_n and determining its value before entering the for loop.
    //This variable should be a double variable.
    double square_root_of_n = sqrt(n); //This will calculate the value only once.
   
    //Test for prime by checking for divisibility
    //by all whole numbers from 2 to sqrt(n).
    for(int i = 2; i <= square_root_of_n; ++i)   { //This will make sure that, the sqrt() is not calculated for every time.
        if(n % i == 0)   {
            is_prime = false;
            break; //This will make sure that, once a factor is found, not further calculations are made.
        }
    }
   
    //Print results
   
    if(is_prime)   {
        cout << "Number is prime." << endl;  
    }   else   {
        cout << "Number is not prime." << endl;
    }
    return 0;
}

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

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