Bool function for Prime Numbers

[opataris]

I am learning functions now, and have a task to write a function that will determine if a number is prime. There is a second function that determines the range of numbers.
I have it working...sort of. I get the prime numbers, however there are some additional numbers that I cannot figure out how to get rid of.

I dont know if the problem if a math error or a logic error. The logic looks right to me, but as I said, I am just learning.

The numbers I get with a range of 3-33 are:
5 7 9 11 13 15 17 19 21 23 25 27 29 31 33

As you can see, 9, 15, 25, 27, and 33 are NOT prime numbers.

Help please.

 #include <iostream>
#include <cmath>

using namespace std;

// FUNCTION PROTOTYPE FOR read_range
void read_range(int& imin, int& imax);

// FUNCTION PROTOTYPE FOR is_prime
bool is_prime(int k);

// DO NOT MODIFY THE MAIN ROUTINE IN ANY WAY
int main()
{
  int imin(0), imax(0);

  // Read in range
  read_range(imin, imax);

  // Print prime numbers
  cout << "Primes:";
  for (int j = imin; j <= imax; j++) {
    if (is_prime(j)) 
      { 
        cout << "  " << j; 
      }
  }
  cout << endl;

  return 0;
}

// DEFINE FUNCTION read_range() HERE:
void read_range(int& imin, int& imax){
  int x(0), y(0); //Initialize variables
  cout << "Enter minimum and maximum:";
  cin >> x >> y ;
  if(x < 2 || y < imin){
      cout << "Error, enter min > 2, and max > min";
      cin >> x >> y ;
  }
  imin = x;
  imax = y;
  
}

// DEFINE FUNCTION is_prime() HERE:
bool is_prime(int k){
  for(int i = 2; i <= (k/2) ; i++){
  if((k % i) != 0) 
    return true;
  else
    return false;    
  }
return(0);
}

[jonnin]

scrambled logic. try this:

bool is_prime(int k)
{
  for(int i = 2; i <= sqrt(k); i++) //sqrt is sufficient, /2 is too many iterations
  {
   if((k % i) == 0)  //if it divides evenly by any value
    return false;       //we are done, its not prime
  }
 return true;  //and outside the loop, if nothing divided it by now, its prime. 
}

yours returns true if the first thing you tried was not evenly divided, without checking other loop values to see if it was prime. do you see this now?

also little things, 0 is false, sure, but a bool function should return either true, false, or the result of a logic statement that returns true or false (eg return x<3). Return 0 is a small style problem (on top of the logical issue).

[tpb]

Although it can almost certainly be optimized out, it may be better to calculate the sqrt before the loop. You can also check divisibility by 2 separately and only check odd divisors after that. It's also a good idea to check for values less than 2, since they are also non-prime.

bool is_prime(int n) {
    if (n <= 2) return n == 2;
    if (n % 2 == 0) return false;
    int sqrt_n = sqrt(n);
    for (int i = 3; i <= sqrt_n; i += 2)
        if (n % i == 0)
            return false;
    return true;
}

[opataris]

Thank you for the replies. I tried it jonnin's way, and I still got the same numbers.
Primes: 5 7 9 11 13 15 17 19 21 23 25 27 29 31 33

Then I tried it tpb's way and it works.
Enter minimum and maximum:3 33
Primes: 3 5 7 11 13 17 19 23 29 31

In reply to tpb, the range was already set to ignore numbers less than two by the other function read_range(), isnt it?

I am still trying to run through the for loop iterations to figure out why it works, and the other one doesnt.
Is there not a way to display what is going on inside the for loops, instead of trying to do it all in the head? The for loops (nested) are something I still have major problems with figuring out the outputs.

[tpb]

You must have done something wrong testing jonnin's function. It should obviously work.

And you're right about not needing to test for numbers less than 2. But I wrote the function in the most general way so that it would be useful no matter what the input.

And I don't see any nested loops.

[opataris]

The for loops are not nested in the technical sense, but the first for loop in main has a function and it calls the second function, which also has a for loop.
The two for loop's work together just as a nested for loop does , doesnt it?

As for jonnin's, you are correct. I tried it again, (copy and paste) and that one worked too.
Here is the difference:
bool is_prime(int k){
for(int i = 2; i <= sqrt(k) ; i++){
if((k % i) == 0)
return false;
else
return true;
}
return(0);
}

I changed everything except for the last return. Its the "return true" inside the for loop that gives the extra numbers. Move the "return true" outside the for loop and those extra numbers disappear. I dont quite understand why.

If I try to think through it, at lets say number 9 (for the "j" of the first loop) , which is the first wrong number, I guess when "i" gets to 9, its ==0 and thus gives a return of false.

I dont understand how moving the "return true" would change that.
I also dont understand how the second loop knows what the value of "k" is?

Like I said, for loops confuse me. I must be missing one fine point or something in the way it works.

[tpb]

When the return true is inside the loop, it will return true the first time k doesn't divide evenly by an i. But it should only return true if k doesn't divide evenly by ALL i's. That's only possible if the return true is outside the loop, where it will execute if and only it none of the i's divided k evenly, i.e., only if the loop ends.

So with the return true inside the loop, if you pass 9 as k, then i starts at 2, which doesn't divide evenly, so it returns true right away. That's the problem.

[opataris]

Thank you so much for taking the time to help me. I appreciate it, truly.