Boolean exercise that needs help with

This is a discussion on Boolean exercise that needs help with within the C++ Programming forums, part of the General Programming Boards category; this is an example code from the book: Code: #include <iostream> #include <math.h> using namespace std; main() { int n; ...

  1. #1
    Registered User
    Join Date
    Sep 2008
    Posts
    65

    Boolean exercise that needs help with

    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?

  2. #2
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    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?

  3. #3
    C++まいる!Cをこわせ! Elysia's Avatar
    Join Date
    Oct 2007
    Posts
    22,455
    Furthermore, main must return int or the code will fail to compile at all.
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.

  4. #4
    Registered User C_ntua's Avatar
    Join Date
    Jun 2008
    Posts
    1,853
    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.

  5. #5
    Registered User
    Join Date
    Sep 2008
    Posts
    65
    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.

  6. #6
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    21,457
    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.
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  7. #7
    Registered User
    Join Date
    Sep 2008
    Posts
    65
    Quote Originally Posted by laserlight View Post

    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!

  8. #8
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    21,457
    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 &#37; i == 0. The break causes control to break from the while loop immediately.
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  9. #9
    Registered User
    Join Date
    Sep 2008
    Posts
    65
    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 &#37; 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.
    Last edited by kenryuakuma; 09-21-2008 at 10:08 PM.

  10. #10
    Registered User
    Join Date
    Sep 2008
    Posts
    65
    Hope somebody could help!

  11. #11
    C++まいる!Cをこわせ! Elysia's Avatar
    Join Date
    Oct 2007
    Posts
    22,455
    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?)?
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.

  12. #12
    Registered User
    Join Date
    Sep 2008
    Posts
    65
    Code blocks and the book is published in July 2008.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Novice needs help
    By ghaasemi in forum C++ Programming
    Replies: 9
    Last Post: 05-30-2009, 08:20 AM
  2. Line of data input method
    By larry_2k4 in forum C Programming
    Replies: 2
    Last Post: 04-28-2009, 11:34 PM
  3. Tutorial review
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 11
    Last Post: 03-22-2004, 08:40 PM
  4. Request for comments
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 15
    Last Post: 01-02-2004, 09:33 AM
  5. Use struct to create a boolean type
    By skyglin in forum C Programming
    Replies: 6
    Last Post: 06-18-2003, 08:21 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21