prime number generator from jumping into c++

Hi everyone! Stumbled upon this problem from jumping into c++ that asks to write program to generate prime number. I have already written the code with another approach(that doesn't use function and instead, uses two loops.) my code can be found here.( cpp.sh/3vho )
but i can't seem to understand one part of the code shown in the book

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
  (just for reference and big picture, the entire code shown in the book is here.
    later again shown only the part which i don't understand)
  the entire code is: 

#include <iostream>
// note the use of function prototypes
bool isDivisible (int number, int divisor);
bool isPrime (int number);
using namespace std;
int main ()
{
for ( int i = 0; i < 100; i++ )
 {
 if ( isPrime( i ) )
 {
 cout << i << endl;
 }
}
}
bool isPrime (int number)
{
for ( int i = 2; i < number; i++)
{
 if ( isDivisible( number, i ) )
 {
 return false;
 }
 }
return true;
}
bool isDivisible (int number, int divisor)
{
return number % divisor == 0;
}  




NOw what i don't understand:

1
2
3
4
5
6
7
8
9
10
11
bool isPrime (int number)
{
for ( int i = 2; i < number; i++)
{
 if ( isDivisible( number, i ) )
 {
 return false;  //tag 1. don't understand this part
 }
 }
return true;  //tag 2. don't understand this part as well
} 


1.when the number being tested is divisible (i.e returns true by isDivisible test), then what is the significance of "return false;" in the body of if statement(see tag 1.)

2.in the body of isPrime, but outside 'for' loop, "return true;" is stated.
(see tag 2)won't the "return true;" be executed for all numbers tested in the
isPrime function so that all the numbers tested in the isPrime function return true and thus, print the entire number from 1 to 99.
I hope I could make u understand what i mean. if u didn't understand my question please say so, and i will try to be more explicit.
Any help would be highly appreciated.
I will presume you understand the return statement's function.

The loop counts through every possible integer divisor less than the argument number. If a number is found that evenly divides the argument number, then we know that the argument cannot be prime. So we return false; to terminate the function and return that knowledge to the caller.

However, there is no point inside the loop where we can say that a number is undoubtedly prime -- as we can only know that once having tested all the possible integer divisors.

It is only if the function completes loop that we know that we could not prove it composite with every possible divisor, therefore it must be prime. return true;

Hope this helps.
Last edited on
1
2
3
4
5
6
int max(int a, int b) {
    if (a >= b) {
        return a;
    }
    return b;
}


No this function will not always return b. It will only return b if a is not greater than or equal to b. i.e. the if statement did not evaluate to true.
This is the same case with the prime function. It will only return true if the number being checked is not divisible by any other number less than itself. The for-loop ends and the only thing left to do is say that the number passed the tests and is infact prime
@smac89, shouldn't there be 'else' statement along with 'return b;'(in your example) to achieve what you mean. As in :
1
2
3
4
5
6
7
int max(int a, int b) {
    if (a >= b) {
        return a;
    }
   else{
   return b;}
}

or is it the case that in case of bools, once the first return statement is executed(true or false), rest of the return statement in the code that follows is discarded?!

@duoas thanks for your detailed response. but still have the doubts about the questions i just aksed to @smac89. maybe you could also help. also you said you presumed that i knew about return statement. i tried to explain myself what it meant but couldn't explicitly do so very well. i think i haven't understood the [b]return[b] statement that very well. so could you plz brief me about what it actually means in short.

The return statement is like saying "I'm done!" and the function stops.

The prime number question is much like being told that you might find a journal in your sister's bedroom that you'll want to steal and read.*

The only way to be sure is to actually go into the room and search it, top to bottom, to find the journal. One of two things will happen:

1) You'll find the journal. (Or that the number is composite.) There is no point in continuing to search the room -- you've got what you wanted. It is time to leave the room. (Or terminate the function.)

2) You search everything and finally discover that there is no journal in your sister's room. Having searched it thoroughly, you simply leave the room, sans journal. (Or terminate the function with true -- no composite numbers were found, therefore the number is prime.)

Hope this helps.

* Please be nice to your sisters and don't do stuff like this.
@koopey, you don't need an else. A return statement is short circuiting. This means that as soon as the return statement is reached, nothing else below that return statement is executed and in short the function terminates at that point and execution begins at the next statement after the call to the function.

Better example:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
int max(int a, int b) {
    if (a >= b) {
        return a;
    }
    return b;
}

int main() {
    int a = 5, b = 9;
    int big = max(a, b);

    { // inside max function
        int a0 = 5, a1 = 9;
        if (a0 >= a1) { // Nope
            // return a0; => skip
        }  //             => skip
        // return a1      => return a1 to main
    }
    
    
    // code execution begins on next line    
    std::cout << std::boolalpha << (b == big) << std::endl; // this should print true
    
    return 0; // return value of zero to OS
}


You can put the else statement there if you want, but it doesn't make a difference because when the if statement evaluates to true, the else will never be executed. But if the if statement evaluates to false, then the only left to do is to execute whatever is in the else and this would have been executed anyways regardless of if you had the else in there or not.
Last edited on
@smac 89 thank you for such a detailed response. now everything regarding the question is clear to me. thanks again.
Topic archived. No new replies allowed.