0

I'm having trouble with this C++ code. The integer num is a number that I want to check if it is prime. However this program is always returning false. It's probably something simple but I can't find anything.

for(int i=2;i<num;i++){ //primes are allowed to be divided by 1 so we start at 2
        if(num % i == 0){ //can be divided by a number other than itself or 1 so we trip out
            return false;
        } else if(i == num){ //if we've already done checks as high as possible and not tripped out yet then report success
            return true;
        }
}
ereOn
  • 53,676
  • 39
  • 161
  • 238

6 Answers6

7

i == num will never occur, since your loop condition is i<num. Try:

for(int i=2;i<num;i++){ //primes are allowed to be divided by 1 so we start at 2
    if(num % i == 0){ //can be divided by a number other than itself or 1 so we trip out
        return false;
    } else if(i == num-1){ //if we've already done checks as high as possible and not tripped out yet then report success
        return true;
    }
}

As pointed out below, the else condition here is redundant, and you only need to check from 2 to sqrt(num) - since the remaining factors have already been checked.

There are more improvements that can be made depending on how complex you want to make the problem. Most methods in reality use probabilistic algorithms.

Flash
  • 15,945
  • 13
  • 70
  • 98
  • 2
    for(i==2;i – Luka Rahne Aug 01 '12 at 06:48
  • There is no need to iterate till `num`. Iterating till `num/2` is enough. – cppcoder Aug 01 '12 at 06:52
  • 3
    I would even suggest `for(i==2;i*i<=num;i++){if(num%i==0) return false} return true;`. – Axel Aug 01 '12 at 06:52
  • @Axel: Better is `for (i = 2; i <= num/i; ++i) { if (num%i == 0) return false; } return true;` as avoiding the multiplication means there's no possibility of integer overflow. – jahhaj Aug 01 '12 at 07:02
  • Why the else? If you fall out the loop without returning, then it's a prime. It makes the code much easier to understand. – Tom Tanner Aug 01 '12 at 07:02
  • There is no need for the last check `i == num - 1`. Just put the `return true` statement outside the loop, at the end of the function. – ereOn Aug 01 '12 at 07:07
  • 1
    correct max is const int maxvalue = static_cast(sqrt(num)); – AndersK Aug 01 '12 at 07:13
  • @Anders K: Correct, but then you do 2 conversions (int -> double and back again) plus a floating point sqare root calculation. You'd have to measure if the overhead doesn't actually slow down (this also depends on the value of num). – Axel Aug 01 '12 at 08:00
  • @Axel : If `num` is so small as to make avoiding floating-point code more efficient in this context, then one would be better with a hardcoded array of some _small_ N primes to begin with. – ildjarn Aug 01 '12 at 08:05
  • 2
    Everyone seems to be complicating things unnecessarily with multiple returns, break, etc. Why not just simply: `int limit = sqrt(num); int i = 3; while ( i <= limit && num % i != 0 ) i += 2; return i <= limit;` (with an initial test for even numbers, of course). – James Kanze Aug 01 '12 at 08:22
  • @JamesKanze: I honestly don't think that one is less complicated. More code, more conditions, but less break/return statements - it all depends on how you measure complexity. – Axel Aug 01 '12 at 12:36
  • 1
    @Axel I don't see more code, nor more conditions. And there are several established measures for complexity. (There is more code if you do as I suggest: check for even first, then iterate from 3 with a step of 2. But that's an optimization that you might want to do anyway.) – James Kanze Aug 01 '12 at 15:07
  • @JamesKanze: i <= limit, num % i != 0, and then again i <= limit. But I think we don't have to argue over this. I think this is just some kind of programming exercise. – Axel Aug 02 '12 at 05:03
  • Yes, I'm doing this for practise and don't need an amazingly effecient program :) –  Aug 02 '12 at 19:27
4

You don't have to check every number, as a lot of them can easily be ruled out. For example, after checking that num is not divisible by 2, you can skip all other even numbers. That saves you half the tests.

We also definitely know that any other factor must be less than num/2 (or really sqrt(num), but that is harder to compute). That knowledge can save us another half of the tests.

So now we have:

if (num % 2 == 0)
    return false;

for(int i = 3; i < num / 2; i += 2){ 
     if(num % i == 0){ //can be divided by a number other than itself or 1 so we trip out
         return false;
     }
}

// arriving here we have found no factors, so it must be a prime
return true;
Bo Persson
  • 90,663
  • 31
  • 146
  • 203
  • 1
    "*(or really `sqrt(num)`, but that is harder to compute)*" But you have the code in that very sentence. ;-] – ildjarn Aug 01 '12 at 07:54
  • Since you ve mentioned, do computing sqrt really overweigh going from srqt -> num/2 ? Won't we get any advantage by stopping at sqrt since computing sqrt is expensive? – Mohan Aug 01 '12 at 07:54
  • I'm just picking some low-hanging fruit here, cutting away 75% of the run time. Anything else we do will obviously just affect the remaining 25% - is it worth the extra effort? It depends. – Bo Persson Aug 01 '12 at 08:01
  • 1
    @MohanKumar Unless `num` is very small, `sqrt(num)` is going to be significantly less than `num / 2`, which means a lot less times through the loop. And on modern machines, `sqrt(num)` shouldn't be very expensive either. – James Kanze Aug 01 '12 at 08:19
  • When computing `num % i` some hardware, like the x86, also delivers `num / i` as a byproduct. We could use that as a continuosly shrinking upper limit. – Bo Persson Aug 01 '12 at 08:40
  • Thanks. I actually already had ruled out all evens except two, but didn't show that bit of code. –  Aug 02 '12 at 19:24
  • @BoPersson (years alter...) "use that as a continuosly shrinking upper limit." this doesn't apply here as we stop on the very first successful division without remainder (and return false). – Will Ness Oct 26 '14 at 19:26
1
bool CheckPrime(int num) {
    bool yayornay = true;
    for(int i = 2; i < num; i++) {
         if(num % i == 0) {
             yayornay = false;
             break;
         }
    }
    return yayornay;
}
Mohan
  • 1,850
  • 1
  • 19
  • 42
JP_
  • 1,636
  • 15
  • 26
  • No `break`? Excessively inefficient. – ildjarn Aug 01 '12 at 07:58
  • 1
    @JeffSchweigler you missed a brackets for if. Without braces, your code will break in the first iteration. Edited to correct the same. – Mohan Aug 01 '12 at 08:57
  • Are you talking about line four? I purposely left out brackets and made line five inline so it didn't need them. =) – JP_ Aug 01 '12 at 15:52
  • Putting multiple statements on the same line does not group them together somehow. @Mohan is right. – ildjarn Aug 02 '12 at 03:57
1

A small optimization for Will Ness's code, just calculate the sqrt of the number outside the for. The condition check executes many times and has no sense to calculate sqrt each time.

if( num == 2 ) return true;
if( num < 2 || num % 2 == 0 ) return false;
int sqrt = sqrt(num);

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

So far I think that this is the most efficient way!

Zelter Ady
  • 6,266
  • 12
  • 48
  • 75
  • I assumed compiler will perform that optimization. :) btw I've made an edit to the code which should make it about 30% faster I think. – Will Ness Aug 01 '12 at 12:45
0

Here's the proper way to write what you meant:

int i=2;                     // move declaration out
for(/*int i=2*/;i<num;i++){ 
        if(num % i == 0){ 
            return false;
        } // else            // and the final test too
}
if(i == num){                
    return true;
}

But that's not efficient. You only have to check for i's not exceeding of sqrt(num). Plus, if you check num%2, there's no more need to check any other even numbers, so you can use an increment of 2. Or you can even count by 6:

if( num == 2 || num == 3 ) return true;
if( num < 2 || num % 2 == 0 || num % 3 == 0 ) return false;
for( int i=5, j=7, lim=sqrt(num); i<=lim; i+=6, j+=6 ){   
        if( num % i == 0 || num % j == 0 ){ 
            return false;
        } 
}
return true;

(notice: this is more efficient than another answer here, which says it's an "optimization" of an initial version of this answer).

Will Ness
  • 70,110
  • 9
  • 98
  • 181
0
bool isprime(int n)
{
    if(n<2) return false;
    if(n==2)return true;
    for(int i=2;i<=sqrt(n);i++)
        if(n%i==0) return false;
    return true;
}
ani627
  • 5,578
  • 8
  • 39
  • 45
Rajeev
  • 1
  • Your solution is very similar to that of @ZelterAdy. However, his algorithm is even more efficient than yours. So what's your reason of posting yet another solution that doesn't provide any added value? – honk Oct 25 '14 at 14:11