Prime number between 2 bounds

[Ricardo R]

Hello!

I have most of this code done, but whenever I run it, It gives me mostly prime numbers with some non-prime mixed in (like 15 and 21). Can anyone point me in the right direction?

here is the code so far:


/*
File: isprime.cpp
Created by: Ricardo Renta
Creation Date: 11/8/11
Synopsis:
This program reads in a minimum and maximum integer greater than 1
and returns all primes between the minimum and maximum.
*/

#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); //boolean prototype for true and false



int main()
{
int imin(0), imax(0);

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

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

return 0;
}

// DEFINE FUNCTION read_range() HERE:
void read_range(int& imin, int& imax)
{
cout << "Enter a minimum and maximum value:";
cin >> imin >> imax;

while (imin < 2 || imax < 2 && imin > imax)
{ cout << "The minimum and maximum values must be at least 2. Please try again."<< endl;
cin >> imin >> imax;
}
}





// DEFINE FUNCTION is_prime() HERE:
bool is_prime(int k)
{

for (int i=2; i<=(k-1); i++)
{
if (k%i==0 && k!=i)
{return false;}

else
{return true;}
}

}

[tfityo]

bool is_prime(int k)
{

for (int i=2; i<=(k-1); i++)
{
if (k%i==0 && k!=i)
{return false;}

else
{return true;}
}

}

is wrong. During the first iteration in the loop it tests if k is even. If it is even then the function returns false, otherwise it returns true.

You may try to modify its text as follows:

bool is_prime(int k)
{

for (int i=2; i < k / 2; i++) //you don't need to check all numbers, k/2 is enough or even sqrt(k)
   if (k%i==0) // k is never equals to i 
         return false; 

return true;
}

[Ricardo R]

Hmmmm....I tried the sqrt(k) before, and it didn't work. I tried changing it to what you suggested, and when I put the lower and upper bounds as 3 and 15, respectively, it gave me this output:

Primes: 5 7 9 11 13 15

which is obviously incorrect

[tfityo]

Did you properly copy my function?

Because on my machine, such a code:

#include<iostream>
using namespace std;

bool is_prime(int k){

        for (int i=2; i < k / 2; i++) //you don't need to check all numbers, k/2 is enough or even sqrt(k)
                   if (k%i==0) // k is never equals to i
                                    return false;

        return true;
}

int main(){
        for (int i = 2; i < 20; i++)
                if (is_prime(i)) cout << i << endl;

}

produces the following output:

2
3
4
5
7
11
13
17
19

Neither 9 nor 15 is included. Only 4 is extra.
So, little change from for (int i=2; i < k / 2; i++) to for (int i=2; i <= k / 2; i++)

bool is_prime(int k)
{
for (int i=2; i <= k / 2; i++)//you don't need to check all numbers, k/2 is enough or even sqrt(k)
   if (k%i==0) // k is never equals to i 
         return false; 

return true;
}

corrects everything and produce proper output.

[Ricardo R]

okay, got it. Thank you! But why does checking for k/2 do the trick? I really want to know how/why that works.

[tfityo]

It doesn't do the trick. The code

bool is_prime(int k)
{
for (int i=2; i<=(k-1); i++)
{
if (k%i==0 && k!=i)
 return false;
}

return true;
}

also work.

In your version of code you will return either true or false just after the first iteration of the loop (i = 2, if k is odd then condition
(k%i==0 && k!=i) doesn't hold and you go to else block and returns true.
After you return the function terminates and its all: the result of function is true for every odd input.

Pay attention that in my version return true; executes at the end of the function body: result is true only if every (k%i==0 && k!=i) fails (i.e. we never executed return false;).

[buffbill]

if 2 is the only even prime why not start the loop at 3 and increment by 2 (and so halve the pain)?

[Pravesh Koirala]

Alternatively,
have you ever heard about Sieve of Eratosthenes?? It works nice when Upper bound is known.