Boolean exercise that needs help with

**kenryuakuma** · 09-21-2008

this is an example code from the book:

Code:

#include <iostream>
#include <math.h>

using namespace std;

main()
{
    int n;
    int i;
    int is_prime;

    is_prime = true;


    cout<< "Please enter a number: ";
    cin>> n;
    i = 2;

       while(i <= sqrt(static_cast<double>(n))){
           if(n % i == 0){
               is_prime = false;
               break;
           }
           i++;
       }


       if(is_prime)
            cout<< "Your number is prime";
       else
            cout<< "Your number is not prime";

return 0;
}

Howerver, in the exercise, it just tells you that you have to optimize it. I have been thinking for couple hours but still find no answer.

This is the question: Optimize the program further by calculating the square root of n just once rather than over and over as was done in the example. To perform this optimization, you need to declare another variable and set it to the square root of n. The type should be double.

Would you please just tell me how and explain in details why?

**tabstop** · 09-21-2008

Would you please just tell me how and explain in details why?

Optimize the program further by calculating the square root of n just once rather than over and over as was done in the example. To perform this optimization, you need to declare another variable and set it to the square root of n. The type should be double.

There's not really anything I can add to that. sqrt(n) doesn't change while you're going through the loop, so why calculate it each time through the loop?

**Elysia** · 09-21-2008

Furthermore, main must return int or the code will fail to compile at all.

**C_ntua** · 09-21-2008

I ll explain the why and you figure out the how.
Every time the while loop is executed the condition is tested. So for every iteration the CPU will test i <= sqrt(n). In order to evaluate this condition the sqrt(n) has to be calculated. Every time. But sqrt(n) doesn't change inside the while-loop because n doesn't change. So why calculate it for every iteration? Note that if you have i <=0 then you just have to make one test. If you have i <= 1-1 then you have to evaluate 1-1 and then make a test.

**kenryuakuma** · 09-21-2008

I don't even know why...but the exercise requires you to do that in the book. However, it does compile perfectly.

BTW...Here are some more questions I would like to ask because everything I learn is from the book without any instructor.

1. Why does the author have to set the is_prime = true, which is initialized in the beginning? What does it do?
2) Is it possible to put this is_prime = true into the while loop?
3) assuming everything is true, because according to the sample above, if everything is true, the message would be printed your number is prime but since the variable is set to be true, boolean flag, what if it is false, how does the compiler print the message? Doesn't the number always have to be true because of the setting of the boolean in order to print the message? I am so confused with this.

**laserlight** · 09-21-2008

1. Why does the author have to set the is_prime = true, which is initialized in the beginning? What does it do?

It is basically a "flag" used to record whether the number is prime or not. The idea is this: let's assume that the number is prime. We attempt to prove otherwise by finding a divisor. If a divisor cannot be found after exhausting the set of possible divisors, then our assumption holds and we conclude that the number is indeed prime.

2) Is it possible to put this is_prime = true into the while loop?

Yes, but then that would be a logic error.

3) assuming everything is true, because according to the sample above, if everything is true, the message would be printed your number is prime but since the variable is set to be true, boolean flag, what if it is false, how does the compiler print the message? Doesn't the number always have to be true because of the setting of the boolean in order to print the message? I am so confused with this.

If is_prime is false, then control goes to the else block.

**kenryuakuma** · 09-21-2008

Originally Posted by laserlight

If is_prime is false, then control goes to the else block.

But in the while loop, there is is_prime = false...According to the while-loop rule, it will loop again and again until the number is proven to be true without the "break". It is impossible for the result to be false...Anyway, I am confused myself but here need a slightly clear explanation. Thanks!

**laserlight** · 09-21-2008

But in the while loop, there is is_prime = false...According to the while-loop rule, it will loop again and again until the number is proven to be true without the "break". It is impossible for the result to be false.

You have forgotten about the while loop condition. The loop will loop until the number is proven to be false because a divisor has been found, or i (the candidate divisor) is greater than the square root of the number.

EDIT:
Oh, sorry, I misunderstood what you meant.

The result will be false if n % i == 0. The break causes control to break from the while loop immediately.

**kenryuakuma** · 09-21-2008

Well...However, with further exercises, I am get stuck with this again. It is so annoying. Would you guys please, if possible, spare a few minutes and break down the whole thing and then explain step by step.

1) How is the is_prime = true related to the result of the while-if thing comparison within the middle of the code? I know if n % i == 0, and then we get the false result so what about if(is_prime)? What I know is that since int is_prime has been initialized to be true and then the if would be like if(1) and then print the message of you enter the prime number but what about the false result within the loop? How is it related? And how does it work to get and print the false result because earlier the is_prime has been initialized to be true. Hence, I really need somebody to break this down and show me step by step what each code does. I hope you guys really could help me out. I can't pass this lesson without getting the heck of it.

**kenryuakuma** · 09-21-2008

Hope somebody could help!

**Elysia** · 09-22-2008

Patience.
What is so difficult to understand about the code?
Basically, it initializes is_prime to true in the beginning, because the assumption is that unless that number is proved not to be a prime, it is a prime.
And that's exactly what the loop does. It checks if it's a valid prime number. If it isn't, is_prime is set to false and the loop is aborted.
The program later then checks if the inputted number was a prime or not (via the is_prime flag, which contains the result of the calculation earlier).

And if the code compiles without main returning int, then you have an old compiler and a very old book, as well.
What compiler / IDE are you using (not Turbo C++ I hope?)?

**kenryuakuma** · 09-22-2008

Code blocks and the book is published in July 2008.

Thread: Boolean exercise that needs help with

Thread Tools

Search Thread

Display

Boolean exercise that needs help with

Similar Threads

Novice needs help

Line of data input method

Tutorial review

Request for comments

Use struct to create a boolean type