Question regarding this prime number code.

[wolfcry]

Hey all,

I've been reading C++ Without Fear, which in my opinion is a fantastic book for beginners. However, there's an example in the book teaching about detecting prime numbers from user input but I'm not too sure how it's doing certain things. This is a bit odd I know, but I have a very technical mind and I need to understand the 'mechanics' of what I'm doing in order to learn it.

Please note that I did title the variables but that's only because I am having difficulty grasping this and I was trying to make it easier for myself to follow. So I apologize in advance for this.

here is the code:

#include <iostream>
#include <cmath> // Original preprocessor in book was <math.h>

using namespace std;

int main()
{


int numberProvidedByUser;
int KeyPrimeNumber;
int is_prime;


is_prime = true;

cout <<" Enter number and press ENTER..." <<endl;
cin >> numberProvidedByUser;

KeyPrimeNumber = 2;

while(KeyPrimeNumber <= sqrt((static_cast<double>(numberProvidedByUser)))) {

    if(numberProvidedByUser % KeyPrimeNumber == 0) // Determine if number is evenly divided.
        is_prime = false;

        KeyPrimeNumber++;
}


if(is_prime){

    cout << " Number is prime..." << endl;

}else{

    cout << " Number is not prime. " <<endl;
}



    return 0;
}

Ok, now the part I'm having difficulty understanding is this:

KeyPrimeNumber = 2;

while(KeyPrimeNumber <= sqrt((static_cast<double>(numberProvidedByUser)))) {

    if(numberProvidedByUser % KeyPrimeNumber == 0)
        is_prime = false;

        KeyPrimeNumber++;
}

1. Since 2 is the key prime number, which is just basic math, then how does the loop work when someone enters 1 as the input? Though I realize 1 is considered a 'unit' rather than a 'prime' due to factoring issues it's still technically a prime due to the rule of only-self-and-one-division however, regardless of that, the loop shouldn't run because the square root of 1 is 1 and 2 is not less than or equal to 1. So how is the program 'skipping' the while condition and running anyway?

2. What exactly is KeyPrimeNumber++ doing? I understand that it is incrementing the KeyPrimeNumber value by 1, but why? The loop only runs once so why the incrementation? If I'm understanding the method of incrementation, this is only being done at the end of this code block and therefor if the loop was to 'run again' on it's own, the new KeyPrimeNumber would be 3, 4, 5, respectively with each new loop. This isn't making sense to me and I was hoping someone would explain how this code is working in simple terms.

Thanks all.

[helios]

the loop shouldn't run

Who says it is running?

The loop only runs once so why the incrementation?

In which case does the loop run only once? Always? And what makes you think allows the loop not to continue running?

[firedraco]

Perhaps "KeyPrimeNumber" isn't really the best name for that variable...it's more like it's the divisor that you are testing. Basically the while loop is equivalent to this for loop:

for(unsigned int start = 2; start < sqrt(userNumber); ++start) {
    //loop from 2-sqrt(userNumber)
    if(userNumber % start == 0) {
        is_prime = false; //if the number is divisible by anything in that range, it isn't prime
        break; //exit the loop, don't need to keep testing, since we know it isn't prime
    }
}
//once we get here, is_prime will be true or false depending on our results 

2.) The condition of a while loop is testing each time the loop reaches the end, not just the first time it enters. Again, IMO a for loop is far better for this kind of thing though.

Btw, is_prime should be a bool.

[wolfcry]

@firedraco: Thank you for your explanation. It was really helpful. Though I understand the syntax of the code, I'm not grasping the incrementation part for this particular program.

For example, let's say a user types in 97. The square root of 97 is 9.8 (give or take) so with the incrementation, the loop checks to see if, in your case "start" is less than the square root of the user's number and if it is it 'runs' the code within the block incrementing each time it is ran, stopping when the counter becomes "equal to" the square root. Is this correct? From what I've learned of loops I thought it was.

In the example of the input being 97, how does the loop handle the numbers between 3 and 9? Is the incrementation being handled silently in the background? Because the program only prompts the user once for their input not incrementally.

I really appreciate your help. I do have to admit though I wished you hadn't have provided the for loop code lol. The book had an exercise for optimizing the code into a for loop and I was trying to figure it out lol. It's all good though. The book I'm doing all this stuff out of has nothing to do with any courses I'm taking.

@helios:

Who says it is running?

while(KeyPrimeNumber <= sqrt((static_cast<double>(numberProvidedByUser)))) {

    if(numberProvidedByUser % KeyPrimeNumber == 0)

Wouldn't the program need to "run" the code within the while loop, to ensure the number provided is not an evenly divisable number to produce the correct output? If so, how is the program reaching the end, (producing output to the screen), when the starting number (2) is greater than 1 if the user input was infact the integer 1. It seems, the integer 1 shouldn't allow the program to produce anything. Thanks for your help.

[helios]

Way to completely misunderstand my intention. I was trying to make you question your own statements so that you could arrive at an answer by yourself, which is far more valuable to you than me straight-out telling you. If you don't want to learn to learn (not a typo), then I can just tell you in precise steps what the program will do, when, and why.

how is the program reaching the end, (producing output to the screen), when the starting number (2) is greater than 1 if the user input was infact the integer 1. It seems, the integer 1 shouldn't allow the program to produce anything.

A while simply does this:
1. If the condition is false, go to step 4, otherwise, continue with step 2.
2. Run the block.
3. Go to step 1.
4. Continue with the program.
The only case when 4 is not reached is when the condition never becomes false (i.e. an infinite loop). If the condition is false from the beginning, the statement behaves like an if statement, skipping the block entirely.
If the control flow isn't looping endlessly and it hasn't returned to the caller -- which in this case it hasn't, because the only return is at the bottom of main() -- then the only place it can go is down. It won't just magically disappear simply because a condition turned out to be false. It has to go somewhere.

[wolfcry]

Hi helios,

I'm really sorry. The way I originally read your reply came off wrong and again, I'm sorry. I hope no harm has been done. I modified my reply to you to remove the unnecessary comments. As far as 'just telling me', not at all. I will never learn that way and all help, even thought provoking help, is greatly appreciated.

Ok, I think I'm understanding you. So using your step list this is what's going on?

1. Program runs, user inputs number (1), program checks starting number (2) and the <= condition is found to be false and automatically skips everything in the while loop block including the incrementation. So nothing has been incremented because of the skip because it didn't need too.

2. Program goes to the if statement outputs the "is prime" statement because it was not found to be false because the inital <= condition check was false and nothing was checked against it.

Then this answers my question from above in regards to the example of user input being 97. Since the <= condition was found to be true, then the loop runs automatically (silently in background essentially), increasing the start number to provide a way to 'break' out of the loop printing any output from the if statement. And because it happens so fast, the user doesn't even notice the incrementing loop.

I hope I'm on the right path there because it's starting to become really clear now. Thank you very much for your help!

Now, I have a question regarding this code snippet:

is_prime = true;
Is that significant to have? Coding or professional wise? I removed it but the program ran as it should have with no warnings.

[helios]

Is that significant to have? Coding or professional wise? I removed it but the program ran as it should have with no warnings.

Where else is the variable set? Is it possible for the program not to reach that point given a certain input? What would be the output if it didn't? Remember that the value of uninitialized variables is unpredictable.

[wolfcry]

To be honest, I'm pretty stumped on this one. So I'll do my best here.

Where else is the variable set?

is_prime = false;

It's set there and used here:
[code]if(is_prime){

cout << " Number is prime..." << endl;
}code]

Is it possible for the program not to reach that point given a certain input?

As far as I know, no. I've tried using a variety of different inputs (characters, symbols, negative numbers etc.), and nothing caused an error while running or caused the program to crash or stop in anyway. Honestly, I don't know on this one.

What would be the output if it didn't?

Unless the while loop condition was true and the is_prime flag was triggered for false, the output would be "is prime" because there wouldn't be a check against it? This seems to be the case whenever I run the program.

[helios]

As far as I know, no. I've tried using a variety of different inputs

Did you try with 1?

[wolfcry]

I did and it always comes back as "number is prime."

Here's the list of what all I tried:

letter = "Number is not prime"
symbol ($,@ etc) = Number is not prime
1 = number is prime
-1, - 2 etc, = number is prime
0 = number is prime.
+9,*9,/9 = all came back as not prime number.

No matter what I do, nothing causes the program to stop running or throw an error.

From what I gather the "is_prime = true" is declared in the beginning in case there isn't any divisor, but I have the divisor set to 2 so there will always be a 'true' condition because it's a non-zero. Is that right? so the "is_prime = true" isn't really needed for the program to run properly?