Bool Question

[kenryuakuma]

Well...It looks fairly simple and I could do this myself. But one thing I don't understand is how come doing a prime number test requires assuming a number is true in the very beginning of the main function. Here is an EXAMPLE of the book I bought, and I think it was published and released after 2001, which is a bit old and sounds out-dated. Anyway, here it is:

#include <isotream>
#include <cmath>
using namespace std;

int main() {
        int n;     // Number to test for prime-ness
        int i;      // Loop Counter
        int is_prime;  // Boolean Flag. For new compiler, it is better to use bool rather than int

        // Assuming that a number is prime until proven otherwise
        is_prime = true;
        
        cout << "Enter a number and press ENTER: ";
        cin >> n;
        
        // Test for prime-ness by checking for divisibility by
        // all whole numbers from 2 to sqrt(n)
        i = 2;
        while (i <= sqrt(static_cast<double>(n)) {
             if (n % i == 0)
                   is_prime = false;
              i++;
         }

         if (is_prime)
             cout << "Number is prime.";
         else
             cout << "Number is not prime.";
 }

Question 1: Well, when doing the prime test, do we always NEED TO ASSUME the number is TRUE by doing is_prime = true;? What's the benefit of doing that?

Question 2: Since stating is_prime is true, that means is_prime = 1. So in the if(is_prime) decision making, it will always print the message, "the number is prime." But what about if the number is not prime, and that means it gets the remainder, so how does it print the message? Unless if(is_prime) = 0, the message will never work and this is based on my own understanding. But in logic, it does work. My question is HOW IT WORK, and I need step by step explanation here.

Question 3: Based on my understanding, if_prime = false, which is located in the while loop and if the number is not prime, which means it gets the remainder, when it is done, where is this value stored? since is_prime has been assumed to be true is_prime = true. Isn't there a contradiction true vs false? I am confused at this point as well. Since true has been assigned to if(is_prime), if false is assigned to if(if_prime), that will contradict one another.

Question 4: Instead of placing the assumption at the beginning of the main function, is it possible to place it within the while loop, same as the is_prime = false?

How the whole thing works is still a mystery to me. And the book does not explain this point in real clarity.

[Gumbercules]

as a variable, is_prime can be chaged from false to true. This code sets is_prime to false when a factor is found. Setting it true at first, and having it set to false after a factor is found assures that is prime will be true in the other case, i.e. prime.
is_prime could only be set to true in the wile loop if a break is also put in the if condition, otherwise if it is set to false it will be set to true again the next time it finds a factor.

[buffbill]

Once having divided the number by 2 it is redundent to divide it by any other even numbers. After 2 it is only necessary to divide by 3, 5, 7....etc.
The following is more effecient.

{
sqrtn=sqrt(n);
if(n<2)return false;//0 and 1 are not prime
if(n<4)return true;//2 and 3 are first primes
if(n%2==0)return false;//2 is only even prime
for(int i=3;i<=sqrtn;i+=2)
   if(n%i==0)return false;//n has a non trivial devisor
   else return true;
}

hope this helps.

[kenryuakuma]

Thanks for you optimization of the code Buffbill.

Still have some questions Gumbercules...Well...Is it possible to place is_prime = true and is_prime = false within the while loop. That's, after the if statement to create compound statement? Or will it also be ok to place both is_prime = true and is_prime = false at the very beginning of the main function as above?

is_prime could only be set to true in the wile loop if a break is also put in the if condition, otherwise if it is set to false it will be set to true again the next time it finds a factor.

When you mentioned, "otherwise if it is set to false it will be set to true again the next time it finds a factor." I am kind of confused about what you mean by otherwise if it is set to false it will be set to true again the next time it finds a factor.

[Gumbercules]

I'm sorry, I said that backwards. If it finds a factor, is_prime should be false, but if there is no break, the loop will continue with the next number, and if it does not divide, is_prime will be set to true again (if is_prime = true was put in the while loop)

This should work, but if you remove the break it shouldn't.

int main() {
        int n;     // Number to test for prime-ness
        int i;      // Loop Counter
        int is_prime;  // Boolean Flag. For new compiler, it is better to use bool rather than in
        cout << "Enter a number and press ENTER: ";
        cin >> n;
        // Test for prime-ness by checking for divisibility by
        // all whole numbers from 2 to sqrt(n)
        i = 2;
        while (i <= sqrt(static_cast<double>(n)) {
             if (n % i == 0) {
                   is_prime = false;
                   break;
             } else
                   is_prime = true;
              i++;
         }

         if (is_prime)
             cout << "Number is prime.";
         else
             cout << "Number is not prime.";
 }

note that the while loop could be written this way:

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

is_prime starts out as true, but gets overwritten to false if a factor is found, making is_prime = true the default case when no factor is found.

Don't think of variables as variables in the mathematical sense, but more as containers to store information. The assignment operator (=) is just that, it puts the right value into the left value, rather than forming a mathematical statement. For example, the line i++ could have been written;
i = i + 1;
While that would be a false statement, or i = empty set mathematically, it's perfectly acceptable here, it just increases the value i is holding by one.